ApproxDet: Content and Contention-Aware Approximate Object Detection for Mobiles

Given an input image or video frame, an object detector aims at locating tight bounding boxes of object instances from target categories. In terms of network architecture, a CNN-based object detector can be divided into the backbone part that extracts image features, and the detection part that classifies object regions based on the extracted features. The detection part can be further divided into two-stage (Ren et al., 2015; Dai et al., 2016) and single-stage detectors (Liu et al., 2016; Redmon and Farhadi, 2018; Lin et al., 2017). Two-stage detectors usually make use of Region Proposal Networks (RPN) for generating regions-of-interest (RoIs), which are further refined through the detection head and thus more accurate.

Our work builds on Faster-RCNN (Ren et al., 2015) — an accurate and flexible framework for object detection and a canonical example of a two-stage object detector. An input image or video frame is first resized to a specific input shape and fed into a DNN, where image features are extracted. Based on the features, a RPN identifies a pre-defined number of candidate object regions, known as region proposals. Image features are further aggregated within the proposed regions, followed by another DNN to classify the proposals into either background or one of target object categories and to refine the location of the proposals. Our key observation is that the input shape and the number of proposals have significant impact to the accuracy and latency. Therefore, we propose to expose input shape and number of region proposals as tuning knobs in ApproxDet.

Another line of research develops single-stage object detection (Liu et al., 2016; Redmon and Farhadi, 2018). Without using region proposals, these models are optimized for efficiency and oftentimes less flexible. We consider one of the representative single-stage detectors as a baseline (Redmon and Farhadi, 2018) in our experiments. YOLO simplifies object detection as a regression problem by directly predicting bounding boxes and class probabilities without the generation of region proposals.

Object tracking seeks to locate moving objects over time within a video. We focused on motion-based visual tracking due to its simplicity and efficiency. A motion-based tracker assumes the initial position of each object is given in a starting frame, and makes use of local motion cues to predict the object’s position in the next batch of frames. Our system considers a set of existing motion-based object trackers — MedianFlow (Kalal et al., 2010), KCF (Henriques et al., 2014), and CSRT (Lukežič et al., 2018). The key difference lies in the extraction of motion cues, via e.g., optical flow or correlation filters, leading to varying accuracy and efficiency under different application scenarios. We thus propose to enable the adaptive choice of the trackers as one of our tuning knobs.

Another important factor of object tracking performance is the input resolution to a motion-based tracker. A downsampled version of the input image allows to better capture large motion and thus to track fast-moving objects, while a high-resolution input image facilitates the accurate tracking of objects that move slowly. Therefore, we further expose the downsampling ratio of the input image as another tuning knob for tracking.

Many computations are inherently approximate—they trade off quality of results for lower execution time or lower energy. Approximate computing has emerged as an area that exposes additional sources of approximation at the computer system level, including resource-constrained mobile and embedded platforms. One challenge in approximate computing is that the accuracy and performance of applying approximate techniques to a specific application and input sets are hard to predict and control (Mitra et al., 2017; Ding et al., 2015; Ansel et al., 2011). This may lead to missed optimization opportunities, unacceptable quality outputs, and even incorrect executions. The two fundamental causes is that approximation techniques are not content-aware and contention-aware. Some recent work has started to address these issues. For example, Input Responsive Approximation (IRA) (Laurenzano et al., 2016) and VideoChef (Xu et al., 2018a) have brought in content-aware approximation for image processing and video processing pipelines respectively.

To the best of our knowledge there is no solution that makes video analytics on mobile platforms adaptive to resource contention. Recently, Min et al. (Min et al., 2019) assess the runtime quality of sensing models in the multi-mobile-device environment so that the best device is selected as a function of model accuracy. However, we have not seen similar work on the video object detection task. There are several works that provide tunable knobs to trade off accuracy-versus-latency, primarily in the image processing context (Huang et al., 2018; Fang et al., 2018; Yang et al., 2020), and some in video processing context (Chin et al., 2019). It is conceivable that these knobs can be reconfigured to an optimal setting continuously as contention varies. However, there are key systems challenges that have to be solved before that end goal can be achieved. Such challenges include how to sense contention, how to change the knob in response to a specific level of contention, and how to optimize for the switching overhead from one approximation level to another.

To support the runtime adaptive object detection framework on videos, we first design a multi-branch object detection framework, with light switching overheads between different branches so that it can quickly adapt to runtime changes. Different from object detection on still images, videos have temporal similarities and an object tracker is widely used to reduce the runtime cost with minor accuracy drop. Similarly, we compose an object detection DNN and an object tracker. The detection DNN produces initial bounding boxes for each object in the input image, while the tracker tracks objects between successive frames.

The overwhelming majority of work on lightweight object detection (such as that suited for our target class of devices, mobiles or embedded devices) is for images, such as YOLOv3 (Redmon and Farhadi, 2018) and SSD (Liu et al., 2016) and thus, does not leverage the video characteristics inherent in relation across image frames. For us, this leads to several insights and guides several design decisions.

For the detection DNN, we choose the popular Faster-RCNN with ResNet-50 as the backbone (Ren et al., 2015). It shows state-of-the-art performance with medium speed when compared with other detection models. For the tracker part, we experiment with a set of 4 trackers — MedianFlow (Kalal et al., 2010), KCF (Henriques et al., 2014), CSRT (Lukežič et al., 2018), and Dense Optical Flow (Farnebäck, 2003). These trackers are open-sourced in OpenCV with reasonable performance. We then expose five tuning knobs for this object detection framework that our scheduler controls programmatically at runtime to achieve the right accuracy-latency tradeoff. We introduce them below and illustrate them in Figure 3.

• •

  Sampling interval ($si$): For every $si$ frame, we run the heavyweight object detection DNN on the first frame and light-weight object tracker on the rest of the frames.

• •

  Input shape ($shape$): The resized shape of the video frame that is fed into the detection DNN.

• •

  Number of proposals ($nprop$): The number of proposals generated from the Region Proposal Networks (RPN) in our detection DNN.

• •

  Tracker type ($tracker$): Type of object tracker.

• •

  Down-sampling ratio ($ds$): The downsampling ratio of the frame used by the object tracker.

Generally, we have empirically observed that smaller $si$, larger $shape$, more $nprop$, and smaller $ds$ will raise the accuracy and vice-versa. We will discuss the specifics of the knobs in Section 5.1.

As multi-branch object detection framework is designed, an important prerequisite is to precisely estimate the accuracy and computation time (latency) of each approximation branch. To start with, the content feature has great impact on both the accuracy and latency of each AB based on the following two observations – (1) tracker latency is affected by the number and area of the objects because tracker algorithms take the bounding boxes of the detection frames as inputs and calculate features inside each box; (2) both detection and tracker accuracy are affected by the content in the video. For example, detection DNNs perform consistently poorly with small objects on MS COCO dataset, including Faster-RCNN (Ren et al., 2015), SSD (Liu et al., 2016), and YOLO (Redmon et al., 2016). Moreover, both detection DNN and tracker find it harder to deal with fast-moving objects. Some previous works (Chen et al., 2015) mention that movement between frames can be used as a feature to trigger the heavy detection process. This implies that for video object detection systems, we need to extract these content features to improve the accuracy and latency of our models. In this paper, we mainly consider two types of content features, described next.

Latency prediction models aim to predict the frame-wise latency of each AB for future frames. Denote $L_{fr}$ as the per-frame latency of our adaptive object detection framework. $L_{fr}$ is a function of the DNN based detection latency $L_{DNN}$ and the tracking latency $L_{tracker}$. If object detection DNN runs every $si$ frames (sampling interval), the latency $L_{fr}$ is given by

We now describe the models of the detection latency $L_{DNN}$ and the tracking latency $L_{tracker}$, respectively.

Accuracy prediction models aim to predict the expectation of the accuracy of each AB for near future frames. Predicting a model’s accuracy in the future is a very challenging task. To this end, we start with a baseline, content-agnostic accuracy model that models the average accuracy of approximation branches on an offline validation set. Improving on the baseline, we propose a content-aware model that estimates the accuracy based on the input video content.

The accuracy of an object detector is usually defined by the metric mean average precision (mAP). However, we find that predicting the absolute mAPs given a test video is difficult. To address this issue, we propose to convert the absolute mAP metric into a relative percentage metric. More precisely, a base branch is identified in the detection framework using the detection-only branch ($si=1$) with $nprop=100$ and $shape=576$. This base branch sets the performance upper-bound for all approximation branches (62.3% mAP on the validation set). The mAP of each AB is normalized to its percentage value by dividing its mAP by the base branch’s mAP.

Synthetic Contention Generator (CG) is designed as a stand-in for any resource contention on the device that may affect ApproxDet. A detection framework may suffer from unpredictable levels of resource contention when it is running on mobile platforms due to the instantiation of other co-located applications, for which we will not have information. We focus on three important types of resources on mobile platforms — CPU, memory bandwidth (MB), and GPU. We control CPU contention by the number of CPU cores our CG occupies. We control MB contention by the amount of memory-to-cache bandwidth that it consumes. The code is modified from the widely used STREAM benchmark (McCalpin, 2007, 1995) that is meant to measure the MB capacity of a chip. For the GPU contention, we control the number of GPU cores that are utilized. The three-dimensional CG is orthogonal, which means we can tune each dimension without affecting the other dimensions. The CG is representative because we executed and mapped the contention caused by some widely-used applications in the 3D contention space (Table 2). The first one is an anomaly detection program that uses Robust Random Cut Forest (RRCF) (Guha et al., 2016) to detect anomalies from a local temperature and humidity sensor data. We also used our two object detection DNNs, Faster R-CNN and YOLOv3, for checking how much contention they generate.

The cost of collecting ground truth data with design features for performance prediction models is significant without proper sampling techniques. We measure our profiling cost for the accuracy, detection latency, and tracker latency models in Table 3.

To efficiently collect the profiling data, we use the master and worker model, where the master node manages a list of configurations of the detection framework and distributes the profiling work, while workers run the particular configuration to collect the training data for the modeling. As the feature space is huge, we sparsely sample the multi-dimensional space of (“number of proposals”, “resized shape”, “sampling interval”, “tracker”, “down-sampling ratio of the tracker’). We finally use 20% of the configurations to train our accuracy model.

Similar sub-subsampling techniques are used for the latency models as well, and we sample data points on videos of various height and width, various numbers of objects and object sizes, under discrete 3D contention levels. We finally use 15 out of a million feature points (defined in Section 5.2 and  5.1) to train our detection latency model and 169 out of a million feature points to train our tracker latency model.

The scheduler is the core component of ApproxDet that makes the decision at runtime on which AB should be used to run the inference on the input video frames. Formally, the scheduler maximizes the estimated detection accuracy of ApproxDet given a latency requirement $L_{req}$. This is done by identifying a feasible set of branches that satisfy the target latency requirements, and choosing the most accurate branch. In case of an empty feasible set, the fastest branch is returned. Thus, we formulate the optimal AB $b_{opt}$ as follows,

where $\mathcal{\hat{B}}$ is all ABs considered, $\hat{B}$ is the feasible set, i.e., $\hat{B}=\{b\in B\}\ \ \text{iff}\ \ L_{est,b}<L_{req}$, $A_{b}$ and $L_{est,b}$ are the estimated accuracy and latency of the AB respectively. The search space $\mathcal{\hat{B}}$, composed of five orthogonal knobs, has millions of states. To reduce the scheduler overhead, we use a sampling technique in Section 5.1 and design light-weight online feature extractors.

To further reduce the scheduler overhead and enhance our system robustness, we restrict the scheduler to make decision at least every $sw$ frames. The motivation of introducing $sw$ is to prevent the scheduler to make very frequent decisions. Specifically, we set $sw=max(8,si)$. The scheduler will thus make a decision at least every 8 frames. When the scheduler chooses a branch with a long $si$, it will make a following decision every $si$ frames. In addition to the latency of the detection and tracking kernels, we add switching overhead $L_{sw}$ and the scheduler overhead $L_{sc}$ into the overall latency estimation of a AB $b$, i.e., $L_{est,b}=L_{b,fr}+(L_{sw}+L_{sc})/{si}$. We also design the light-weight online feature extractors so that we can adapt seamlessly to the content and contention changes.

The log-based contention sensor tries to find a contention level where the offline latency log matches the averaged online latency most closely. We use the nearest-neighbor principle to search for such contention levels in our pre-defined orthogonal 3D contention space. As multiple contention levels may cause the same impact on the latency of a given AB, we call it a cluster of contention levels and we pick one level out of it as the representative. In comparison to some previous work in the systems community (Fang et al., 2018), our contention sensor is lightweight, efficient, and does not require additional privileges at system level, making it a more practical offering in real-world systems.

Our five tuning knobs include the sampling interval ($si$), the input image size ($shape$) to the detection DNN, the number of proposals ($nprop$) in the detection DNN, the type of object tracker ($tracker$) and the downsampling ratio of the input to the tracker ($ds$). We now describe the implementation details of these knobs, including their data types and value ranges.

The latency and accuracy model in ApproxDet is trained using a subset of the validation set of ImageNet VID. Specifically, we sparsely sample the 5-D feature space $(si,shape,nprop,tracker,ds)$ and run ApproxDet using the sampled configuration on a subset of videos randomly sampled from the validation set. Standard gradient descent is then used for fitting the regression. And CART is used for the decision tree. To train content-aware accuracy model, during the training phase, the $movement$ feature as the average motion across all objects and all frames is required in each video snippet. During the test phase, since movement of the objects are not available, we use average across all past frames as a substitute.

We evaluate ApproxDet on an NVIDIA Jetson TX2 board (Corporation, 2018), which includes 256 NVIDIA Pascal CUDA cores, a dual-core Denver CPU, a quad-core ARM CPU on a 8GB unified memory between CPU and GPU. The specification of this board is comparable to what is available in today’s high-end smartphones such as Samsung Galaxy S20 and Apple iPhone 11 Pro. We train our neural network models on a server with NVIDIA Tesla K40c GPU with 12GB dedicated memory and an octa-core Intel i7-2600 CPU with 24GB RAM. For both the TX2 and the edge server, we install Ubuntu OS and Tensorflow v1.14, Pytorch v1.1, and MXNet v1.4.1.

We evaluate ApproxDet on the object detection task using ILSVRC 2015 VID dataset (Russakovsky et al., 2015). For the purpose of training, since ILSVRC 2015 VID training set is a video dataset, due to the redundant video dataset and limited resources, we follow the practice in (Kang et al., 2017) such that the VID training dataset is sub-sampled every 100 frames. We use 90% of this video dataset as training set to train ApproxDet’s DNN model and keep aside another 10% as validation set to fine-tune ApproxDet (modeling). To evaluate ApproxDet’s system performance, we use ILSVRC 2015 VID validation set – we refer to this as the “test set” throughout the paper. For all our baselines, we follow the data split of ApproxDet’s DNN model to train and test.

We use latency and mean average precision (mAP) as the two metrics. We define the latency as the short-window averaged latency among one detection frame and its following tracking frames. The definition applies to ApproxDet’s baselines with different trackers used. The latency also includes the overheads of the respective solutions, e.g., the switching overhead, the execution time of the online feature extractor, the online contention sensor, and the scheduler. For common detection methods, they will use low confidence threshold, e.g., 0.001 (Ren et al., 2015; Liu et al., 2016) to achieve higher mAP. However, low confidence threshold will lead to many false positive outputs, which is not practical in real-world systems. To simulate the environment of real-world systems, we use a high confidence threshold of 0.3 to reduce the number of output objects of detection DNN, and make it the same for all baseline detection DNNs. Note that we always use the ground truth annotations available in the datatset to examine the true accuracy and never use the detection results of some state-of-the-art models as pseudo ground truth (fake annotations as in (Hsieh et al., 2018)).

In this section, we will introduce baseline models used in our paper.

• •

  Pretrained settings: In AdaScale, they use pretrained models on ImageNet VID + ImageNet Detection (DET). In this paper, ApproxDet and AdaScale both start from ImageNet pretrained models.

• •

  Training sets: In AdaScale, they use ImageNet detection dataset (DET) joint with ImageNet VID dataset and subsample every 15 frames in each VID video. In this paper, we remove all training images in ImageNet DET dataset and we use same sampling techniques (sub-sampled every 100 frames) for training Adascale.

We first examine the end-to-end performance of ApproxDet vs. various baselines. Figure 8 shows a micro-view of the accuracy and 95-th percentile latency ³³3We choose the 95-th percentile latency service level agreement (SLA) because it is a promise to the users that in most cases the latency is below the number and shows much stronger latency guarantee than either mean or median latency. under no contention (G0) and injected 50% GPU contention (G50) from the CG. The reason why our evaluation injects GPU contention only, is that the inference time of the DNN has the most impact on the detection latency and such inferences mostly run on the device’s GPU (when it is available). Hence, the impact of GPU contention would focus on the most interesting scenarios showing how resilient ApproxDet is with respect to changes in the dynamics within the mobile device.

The results show the superior accuracy-vs-latency trade-off (blue vs. green vs. purple) over a FRCNN+MF and YOLOv3 under no contention where particularly, ApproxDet’s accuracy is 11.8%, 9.5% higher than FRCNN+MF given 80ms and 90ms latency SLA and also 9.1% higher than YOLOv3 given 170ms latency SLA (exactly following YOLOv3’s posterior 95-th latency). The accuracy gain over FRCNN+MF reduces as latency SLA grows larger since both ApproxDet and FRCNN+MF will merge into detection-only (or detection in every alternate frame) branch.

Furthermore, when 50% GPU contention is injected, ApproxDet with strong adaptability on sensing and reacting to the contention, the accuracy drops by around 2% and preserves the 95th latency SLA with minor changes (max 16%). However, the best baseline FRCNN+MF cannot adapt to the contention and the latency increases significantly (25% - 50%). Figure 8 shows the performance of FRCNN and AdaScale. Both of their latency increase by 75% to 120% with increased contention levels. This is significantly worse than ApproxDet. Further, FRCNN is inferior to FRCNN+MF in terms of accuracy-latency tradeoff. This is because adding the light-weight MedianFlow tracker largely reduces the latency while preserving most of the accuracy.

Although accuracy vs latency SLA shows the posterior performance metric of each model, we also want to examine under a certain latency requirement, how each solution chooses a model variant to execute and what the accuracy (Figure 10) and the latency violation rates (Figure  10) are. We evaluate at 80ms, 100ms, 150ms, and 300ms. Latency requirement that is smaller than 80ms is not chosen because no branch will be returned from both baselines and larger latency requirement is not meaningful as discussed before. Figure 10 and  10 show that under no contention scenario (GO), ApproxDet and FRCNN+MF are equally good at controlling low latency violations (ApproxDet is slightly smaller), while the accuracy of ApproxDet is 11.8%, 8.5%, 3.0%, and 1.1% higher than FRCNN+MF. Even under great reduction to 80ms latency requirement, ApproxDet is still able to maintain the accuracy above 50%.

Then, as 50% GPU contention is injected, the accuracy of ApproxDet is slightly reduced (by 2%) and is as good as FRCNN+MF under 150ms and 300ms latency requirements. However, ApproxDet is still able to control within the 5% violation rate while FRCNN+MF has a violation rate of 18.3%, 8.0%, 9.5%, and 100%. To summarize, ApproxDet is best at reducing the latency requirement to as low as 80ms with slightly reduced accuracy and is able to adapt well to the contention without violating the latency requirements.

Although the macro benchmark shows the overall performance of ApproxDet on a whole dataset, it is mostly the static behavior of the models since the latency requirement and resource contention levels do not change. To examine how ApproxDet adapts to the runtime changing conditions, we set up these case studies by injecting changing contention levels and latency requirements.

We first examine the performance of ApproxDet given a fixed latency requirement of 100 millisecond on one test video. We then manually inject the GPU contention through CG and gradually tune up the contention level by 20% for every 200 frames. Figure 13 shows that ApproxDet with quick sensing and adaptation, is always able to meet the latency requirements while a FRCNN+MF baseline will either exceed the latency requirement by 20% ($si=20$) or stay too conservative ($si=50$) and suffers from low accuracy (there is a 7% mAP difference between the two branches on the test dataset).

In addition, we also pick a real application—Gaussian Elimination from the Rodinia Benchmark Suite (Che et al., 2009), a GPU-intensive linear algebra routine widely used by many applications. We examine the performance of ApproxDet and baselines without and with the background app. Figure 13 shows that ApproxDet can adapt to the resource contention produced by the background app. The latency goes up dramatically when the app starts running and quickly drops as ApproxDet senses such contention and schedule a more efficient AB. A repeated experiment during the 600—800 frames has further confirmed our adaptability. In contrast, the baseline FRCNN+MF with different $si$ are either too conservative or too aggressive under varying contention levels in terms of latency. When the contention app starts running, there is a larger latency spike of ApproxDet than FRCNN+MF. This is because our system schedules the AB with smaller $si$ as long as the latency of such AB is below the latency requirement. However, since the object detector takes a larger portion in latency and is more sensitive to GPU contention, the latency increase is much higher when the system has not responded yet.

Figure 15 shows a visualization of a heatmap of the switching latency from any approximation branch of the detection framework to another, especially inside the detection DNN. This is an average of 10 such switches and the switching latency is defined as the difference of the execution time of the first frame in the new branches over that of following frames. We can find that switching latency is bounded by 12 milliseconds.

The scheduler overhead comes from the accuracy and latency prediction models, as well as the contention sensor. Generally, the overhead of the scheduler is 11.09 milliseconds per execution. Since we will only execute the scheduler one time during all $si$ frames, the average overhead of the scheduler is under 1 millisecond in most cases. This is supported by the profiling results in Table 5. The overhead of the scheduler occupies less than 1% of the total latency, suggesting that our scheduler is sufficiently fast to satisfy the requirement of an online system.