Spatialyze: A Geospatial Video Analytics System with Spatial-Aware Optimizations

As discussed in § 3 and in line 1 of 1, users construct a World as a first step of S-Flow. Inspired by VisualWorldDB, a World represents a geospatial virtual environment which encompasses Geographic Constructs and Movable Objects, all coexisting with spatial relationships. These relationships, combined with the S-Flow, enable users to describe the videos of interest effectively.

The World also reflects the physical world, where Movable Objects exhibit realistic behaviors, like cars following lanes and adhering to speed limits. We refer to these phenomena as inherited physical behaviors of Movable Objects. We will discuss how Spatialyze leverages these behaviors to optimize video processing in § 6.

Each World has a set of Geographic Constructs; each Geographic Construct has a spatial property that defines its area, represented as a polygon. It also has non-spatial properties including construct ID and construct type. We model each Geographic Construct as $(cid,\allowbreak type,\allowbreak((x_{0},y_{0}),\allowbreak(x_{1},y_{1}),\allowbreak...))$ where $cid$ is its identifier; $type$ is the construct type (e.g., lane, intersection); and $x_{i},y_{i}$ is a vertex of the polygon that represents the construct.

Besides static properties like Geographic Constructs, a World may contain multiple Movable Objects. Being movable, each had spatiotemporal properties, e.g., its location at a given time. Each also has non-spatiotemporal properties, including object ID and object type, that do not change throughout the object’s life span. For example, a Movable Object with object type of “car” will always be a “car.” Spatialyze models each Movable Object as $(oid,type,((l_{0},r_{0},p_{0},t_{0}),\allowbreak(l_{1},r_{1},p_{1},t_{1}),...))$, where $oid$ is its identifier; $type$ is the object type, such as car, truck, or human. At time $t_{i}$, $l_{i}=(x_{i},y_{i},z_{i})$ is its location; $r_{i}$ is its 3D rotation, defined as a quaternion (Kuipers, 1999); $p_{i}$ is its type-specific properties.

A Movable Object with $type=camera$ represents a camera that captures videos. It has a type-specific property $p_{i}=(it_{i},)$, where $it_{i}$ is the intrinsic (Anwar, 2022; Zhang, 2014) of the camera at time $t_{i}$. Despite being Movable Objects, this paper distinguishes the camera from other types of Movable Objects for the following reason. Movable Objects with $type=camera$ are parts of users’ inputs into the World, while Spatialyze infers Movable Objects with other types from the visual contents captured by the cameras.

We do not include “video” as a part of our conceptual data model. A video itself does not have any geospatial property, so it does not exist in a World. Similarly, none of the objects tracked in the video exists initially in the World. Internally only after we bind the video with a camera that captures the video, the video gains geospatial properties from the camera and becomes a part of it. Objects tracked in the video also gain their geospatial properties, as a result of the binding, becoming a Movable Object in the World. Spatialyze derives the objects’ geospatial locations by combining their 2D bounding boxes and the camera’s geospatial information.

Lines 3-4 of 1 defines a Movable Object with $type=camera$ as discussed in in § 4.1.3. Users initialize a Camera from a list, where the $i$-th element of the list is a dictionary with 4 fields: translation, rotation, intrinsic, and timestamp. They correspond to $l_{i}$, $r_{i}$, $it_{i}$, and $t_{i}$, as defined in § 4.1.3.

A GeospatialVideo is a video enhanced with geospatial metadata. A Video (lines 3-4 of 1) by itself contains a sequence of images where each represents a frame of the video. Such video exists spatially in the World after its Video object is bound to a Camera to obtain its spatial properties, where each frame $i$ is an image taken from the camera at location $l_{i}$, rotation $r_{i}$, intrinsic $it_{i}$, and at time $t_{i}$. An object in each frame obtains its geospatial properties after its track is inferred from GeospatialVideo. These objects then become Movable Objects as defined in § 4.1.3.

A RoadNetwork is a collection of road segments. Each road segment is a Geographic Construct as defined in § 4.1.2. Besides being a Geographic Construct, a road segment stores its segment heading, which indicates traffic headings in that road segment. A road segment can have multiple segment headings (curve lane) or no segment heading (intersection). Road segments in the RoadNetwork dataset that we use have the following road types: roadsection, intersection, lane, and lanegroup. In S-Flow, we initialize a RoadNetwork by loading from a directory containing files of the road network from each type. This road network information is accessible and often provided with AV video datasets (Fritsch et al., 2013; Caesar et al., 2019).

Each language construct we introduced so far represents users’ data. Bringing the concept of World described in § 4.1.1 into our DSL, users interact with all of their video data through Geographic Construct and Movable Objects that exists in a World. In a Spatialyze workflow, users interact with the World with this 3-step paradigm: build, filter, and observe. First, users build a World by adding videos and geospatial metadata. Once built, users filter the World to only contain their objects of interest. Finally, users observe the remaining objects through annotated videos.

Build. A World is initially empty. Users add RoadNetwork using addGeogContructs(), followed by adding GeospatialVideo via addVideo(). At this point of the workflow, the World contains Geographic Constructs, and Cameras. Spatialyze uses YOLOv5 (Jocher et al., 2022) and StrongSORT (Du et al., 2023) for object detection and object tracking by default. Spatialyze also supports using UDFs for object detection or tracking, shown as the comment in line 1 of 1.

Filter. Users then construct predicates to filter objects of their interest. As discussed in § 3, Spatialyze has not extracted detections and trackings of objects from the videos yet at this point. Nonetheless, Spatialyze provides an interface for users to interact with these objects as if they already exist. For instance, object() refers to an arbitrary Movable Object with $type\neq camera$ in the World to use in the predicate. Calling multiple object() gives users multiple arbitrary Movable Objects that appear together in the same video. For existing information, camera() refers to an arbitrary Camera. Similarly, geoConstruct(type=...) refers to a Geographic Construct of a certain type. Users can construct a predicate involving multiple Movable Objects, a Camera, or Geographic Constructs, using our provided helper functions. For instance, contains(intersection,obj) determines if intersection as a polygon contains obj as a point. headingDiff(obj,cam,between=[0,9]) determines if the difference of the heading of obj and the heading of cam is between 0 and 9 degrees. In addition, we provide more helper functions and an interface for users to define their own helper functions. Finally, users can chain the filter or use boolean operators to combine predicates.

Observe. After filtering their desired Movable Objects, users observe the filtered World, using one of the following 2 observer functions. First, they can observe the World by watching through snippets of the users’ own input videos. Using saveVideos(file,addBoundingBoxes) function, Spatialyze saves all the video snippets that contain the Movable Objects of interest to a file, where addBoundingBoxes is a Boolean flag that indicates whether the bounding box of each Movable Objects should be shown. Second, they can observe the World by getting the Movable Objects directly. Using getObjects(), Spatialyze returns a list of Movable Objects.

Spatialyze integrates the input data when users Build their World. It processes the Geographic Constructs by creating tables in a geospatial metadata store to store the RoadNetwork and create spatial indexing for every Geographic Construct. Then, it joins each Video and its corresponding Camera frame-by-frame, by their frame number, resulting in a GeospatialVideo.

This stage takes in users’ GeospatialVideo and users’ filter predicates from their workflow’s Filter. It then extracts Movable Objects from the GeospatialVideo. To do so, it first decodes the video to get image frames. It then executes an object detector to extract bounding boxes of objects from each frame. Based on the bounding box, image frame, and Camera, it estimates the 3D location of each object. Finally, it executes the object tracker on the bounding boxes and image frame to get Movable Objects. By default, Spatialyze uses an off-the-shelf algorithm to implement each step. The video decoder is implemented using OpenCV (Bradski, 2000) as it is the fastest option available. The object detector is implemented using YOLO (Jocher et al., 2022), a SOTA object detector used by our prior work (Romero et al., 2022; Xu et al., 2022) with high accuracy, low runtime, and capability to detect multiple types of objects. The object 3D location estimator is implemented using Monodepth2 (Godard et al., 2019) as it is the SOTA image depth estimation that only requires an image as an input. The object tracker is implemented using StrongSORT (Du et al., 2023) as it is a fast and online method, suited for processing large videos.

We designed the video processor to stream video frames through all the above algorithms. Each video frame is pipelined through decoding, object detection, 3D location estimation, and object tracking; hence our video processor only needs to keep $O(1)$ video frames and can handle videos of arbitrary size, addressing the second challenge. While stream processing of videos has been used previously (Broström, 2022), applying it to a streaming video processor is not trivial. For example, the original YOLO-StrongSORT object tracker (Broström, 2022) streams video frames. However, naively extending the tracker with our optimization techniques requires hard-coding them into the tracker’s implementation. This does not scale to future trackers. To solve this problem (and address the third challenge), we implemented our video processor as a plan of streaming operators shown in 2. Our baseline operators¹¹1 The streaming operators internally process videos and geospatial metadata to extract (2D or 3D) object detections and/or tracks. In contrast, users use predicate operators (e.g., contains, distance) to define filter predicates. include: (1) Video Decoder; (2) Object Detector; (3) 3D Location Estimator; and (4) Object Tracker. Specifically, (1) decodes each video to get a sequence of RGB images representing video frames. (2) detects objects in each frame from (1), returning each object and its object type and 2D bounding box. AWorld is 3 dimensional where all objects have 3D locations; therefore, (3) estimates the 3D location of each object from (2) based on its Camera. Lastly, (4) tracks objects by associating detections from (3) between frames. We implemented each operator as an iterator function, where each operator takes in streams of per-frame inputs and returns a stream of per-frame outputs. As a result, our video processor can process videos of arbitrary size, including those larger than the available memory. In addition, we implemented a caching system for the operators. In 2, frames is an input to both ObjectDetector and ObjectTracker. Instead of computing the stream of frames twice, Spatialyze iterates through frames once and caches the results. For instance, a frame $i$ is decoded when the ObjectDetector processes it. Spatialyze caches the frame $i$ so that the ObjectTracker can process it without having to decode the frame again. Spatialyze keeps track of the number of the operators that will be using a cached result and evicts a frame as soon as all of the operators finished processing it; therefore, Spatialyze only caches a few frames at a given time.

Stateless operators like ObjectDetector or Loc3DEstm process each video frame independently. In contrast, ObjectTracker is a stateful operator that keeps track of what objects have been tracked so far at a given frame. To retain states, an ML function can be implemented as a stateful streaming operator using our provided wrapper with minimal changes to the original code of the function.

Executing the plan computes 3D tracks of objects in a video. However, streaming each video through all operators is computationally expensive and not always necessary. Based on the users’ filter predicates from when they Filter the World, Spatialyze only includes the necessary operators in the execution plan. For instance, a predicate based on object types like obj.type=="car" requires objects’ types and hence the execution plan will include lines 1 and 2. Likewise, a predicate with distance or contain functions requires objects’ 3D location and therefore include lines 1, 2, and 3 in the plan. Finally, a predicate with a headingDiff function requires objects’ moving directions and include all lines in the plan.

We implemented each optimization technique in § 6 as a streaming operator. Two of the optimization operators execute users’ predicate early on to reduce the number of inputs (video frames and objects) into later operators. We designed our video processor that constructs plans using streaming operators; therefore, future optimization techniques and video processing functions can be added, addressing the runtime efficiency and extensibility challenges.

This stage takes in users’ filter predicates from their workflow’s Filter and resulting Movable Objects from the video processor. It then filters the Movable Objects with the users’ predicates in 2 steps. First, it streams the Movable Objects into a newly created table in the geospatial metadata store. The table has a spatial index on objects’ tracks and a temporal index on the period, in which the objects exist. Then, it translates the user’s filter predicates into an SQL query and executes it in the geospatial metadata store against the Movable Objects, Cameras, and RoadNetwork. When the user’s predicates involve multiple objects (e.g., distance(car1,car2)<5), Spatialyze self-joins the Movable Objects table to find all objects that coexist in a given period using the temporal index to speed up the join. When the predicates involve spatial relationships between a Movable Object and a RoadNetwork (e.g., contains(road,car)), the spatial index speeds up the joins between the Movable Objects and RoadNetwork tables. We implemented the metadata store using MobilityDB (Zimányi et al., 2020) as it provides necessary spatial and temporal indexes for movement objects. The index along with its spatiotemporal data type are suited for processing queries on Movable Objects and Geographic Constructs.

This stage composes the Movable Objects query results to users’ preferred formats for them to observe. Calling getObjects, Spatialyze returns a list of Movable Objects. Calling saveVideos, Spatialyze encodes the frames containing the Movable Objects into video files with colored bounding boxes annotation.

Fig. 1 shows the execution stages for the workflow in 1. It contains all the stages mentioned above. A user first builds the world by adding data. Spatialyze’s Data Integrator creates an indexed table consisting of RoadNetwork and joins the Video and its corresponding Camera. Then, Spatialyze’s Video Processor creates an optimized video processing plan with 4 processing operators and 4 optimization operators (to be discussed in § 6). Parts of the users’ predicates are executed in Road Visibility Pruner and Object Type Pruner. The Movable Objects Query Engine streams the Movable Objects from the Video Processor into the geospatial metadata store and filters them with the users’ predicates. Finally, as the workflow asks for videos, Spatialyze formats and saves the frames that have the filtered objects into video snippet files.

The Road Visibility Pruner uses Geographic Construct’s visibility as a proxy for a Movable Object’s visibility. Specifically, a predicate includes contains(road,obj) and distance(cam,obj)<d means that obj is not visible in the frames where road is not visible within d meters; therefore, Spatialyze prunes out those frames. In 1, the Road Visibility Pruner partially executes lines 8 where the user searches for “cars within 50 meters at an intersection.” Spatialyze removes all frames that do not contain any visible intersection within 50 meters as these frames will not contain any car of users’ interest.

The Road Visibility Pruner only concerns the visibility of Geographic Constructs. Therefore, it uses Geographic Constructs and Camera to decide whether to prune out a video frame. It uses the intrinsic and extrinsic properties of Camera (Zhang, 2014) to determine the viewable area of each of the cameras according to the world coordinate system.²²2World Coordinate System is a 3-dimensional Euclidean space, representing a World. It then determines if the viewable area of each frame includes any Geographic Construct of interest; frames that do not contain such constructs are dropped and will not be processed in the later processing operators. Since the Road Visibility Pruner will be the first processing operator if applied, it can reduce the number of frames that need to be processed by subsequent ML models in the plan, and hence can substantially reduce overall execution time.

The Road Visibility Pruner works on a per-frame basis. For each video frame $i$ shot by a Camera at location $l_{i}$ with rotation $r_{i}$ and camera intrinsic $it_{i}$, the Road Visibility Pruner performs three steps to determine if the frame should be pruned out. First, it computes the 3D viewable space of the Camera at frame $i$. Then, it uses the viewable space to find Geographic Constructs that are visible to the Camera at frame $i$. Finally, it uses the users’ filter predicates to determine if any Geographic Construct of interest is visible in the frame. We explain each step below.

First, the Road Visibility Pruner calculates the 3D viewable space of the Camera at frame $i$. The viewable space is a pyramid (Fig. 2 side view). (A) is the location of the camera. (B), (C), (D), and (E) represent the top-left, top-right, bottom-right, and bottom-left of the frame at $d$ meters in front of the camera. We compute (B), (C), (D), and (E) by converting the mentioned 4 corner points of the frame from pixel (2D) to world (3D) coordinates. This is done in 3 steps by converting a point from: 1) Pixel to Camera Coordinate System; 2) Camera to World Coordinate System; and 3) Pixel to World Coordinate System.

Pixel to Camera Coordinate System. The equation for converting a 3D point $(x_{c},y_{c},z_{c})$ from camera coordinate system³³3 Camera Coordinate System is a 3-dimensional Euclidean space from the perspective of a camera. The origin point is at the camera position. Z-axis and X-axis point toward the front and right of the camera. The Y-axis points downward from the camera. to a 2D point $(x_{p},y_{p})$ in pixel coordinate system is:

where $it_{i}$ represents the camera intrinsic, a set of parameters representing Camera’s focal lengths ($f_{x},f_{y}$), skew coefficient ($s$), and optical center in pixels ($x_{0},y_{0}$). The intrinsic is specific to each camera, independent of its location and rotation. It converts 3D points from a camera perspective to 2D points in pixels.

To convert a 2D point in pixel ($x_{p}$ and $y_{p}$), we can find the 3D point in the camera coordinate system ($x_{c}$, $y_{c}$, and $z_{c}$) if we know the distance of the point from the camera ($z_{c}$). From Eq. 1, we have:

Modifying Eq. 2 so that the left side is $[x_{c},y_{c},z_{c},1]^{\top}$,

Camera to World Coordinate System. For this conversion, we set up $R$, a $3\times 3$ matrix, representing the 3D rotation of the camera that is derived from the camera’s rotation quaternion. And, $t$ is a 3D vector, representing the camera’s translation. Then, a $3\times 4$ extrinsic matrix $[R|t]$ converts 3D points from camera coordinate system $(x_{c},y_{c},z_{c})$ to 3D points $(x,y,z)$ in world coordinate system:

Pixel to World Coordinate System. Combining the previous 2 conversions in Eq. 3 and Eq. 4 converts 2D points from a pixel coordinate system to 3D points in the world coordinate system:

4 corners of a video frame in the World Coordinate System. To convert the 4 corners of a video frame from pixel to world coordinates, we modify Eq. 5 where we substitute $z_{c}$ with $d$, and $x_{p}$ and $y_{p}$ with actual pixel values representing the 4 corners of the video frame; $w$ and $h$ are the width and height in pixels of the video frame, and each of $B,C,D,E$ is a $3\times 1$ vector representing its 3D location.

After the corners of each frame are translated to world coordinates, the Road Visibility Pruner uses the viewable space to determine the Geographic Constructs that are visible by Camera at frame $i$. Each Geographic Construct’s area is defined using a 2D polygon. Specifically, all polygons representing Geographic Constructs are 2D in the $z=0$ plane. Therefore, the Road Visibility Pruner projects the computed 3D viewable space onto the $z=0$ plane. We define the top-down 2D viewable area as the convex hull (Sklansky, 1982) of the projected vertices (A), (B), (C), (D), and (E) (yellow highlight in Fig. 2’s top view). We then spatially join the 2D viewable area with Geographic Constructs in the geospatial metadata store, using their geospatial indexing created in § 5.2.1. Any Geographic Construct that overlaps with the 2D viewable area is considered visible to the Camera at frame $i$. Once computed, we get visibleGeogs, a set of Geographic Construct types that are visible to the Camera at frame $i$.

Finally, the Road Visibility Pruner uses the users’ filter predicates to determine if there is any Geographic Construct of interest visible in the frame. Examining the contains predicates in the filter, it assigns each contains to $True$ if its first argument is in visibleGeogs and $False$ otherwise. If the value of the transformed filter predicates is $False$, then the Road Visibility Pruner prunes out that frame.

The Road Visibility Pruner has an insignificant overhead runtime compared to the runtime it can save. Our experiments show that the Road Visibility Pruner takes 0.1% of the video processing runtime to execute while saving up to 19.6% of the video processing runtime. So in the worst case that Road Visibility Pruner cannot prune out any video frames, the runtime increase is still negligible. However, having the Road Visibility Pruner in the video processing plan may cause tracking accuracy to drop in some scenarios. Using § 3 as an example, if a car starts at an intersection, exits the intersection, and enters another intersection. When the car is not in any intersection, the camera may not capture any frames containing an intersection. The Road Visibility Pruner will prune out the period of video frames where no intersection is visible to the camera. The object tracker might consider the car before leaving the intersection and the car after entering another intersection to be two different cars.

Spatialyze only needs to track objects of interest as stated in the workflow. The Object Type Pruner prunes out irrelevant objects from being tracked. We analyze users’ filter predicates to look for types of objects that are necessary for computing the workflow outputs. Using the predicates in 1 as an example, the Object Type Pruner partially executes the line 7, where users only look for cars and trucks in the workflow outputs. The trajectories of other objects (e.g., humans) will not appear in the final workflow outputs anyway, so tracking them is unnecessary. Therefore, we only need to input objects detected as cars or trucks into the object tracker to reduce its workload.

The Object Type Pruner reduces the object tracker’s runtime. It has low overhead runtime of 0.06% and does not require geospatial metadata but can reduce up to 69% of the tracking runtime, which is 26% of the video processing time.

Geometry-Based 3D Location Estimator leverages Camera to estimate an object’s 3D locations from its 2D bounding box. It is a substitution for Monodepth2 to estimate objects’ 3D locations. Geometry-Based 3D Location Estimator uses basic geometry calculations and requires 2 assumptions to hold. First, the object of interest must be on the ground. We can then assume that the lower horizontal border of the object’s bounding box is where the object touches the ground. Second, we can identify the equation of the plane that the object of interest is on. In Spatialyze, the plane $z=0$ is the ground, although our algorithm can be modified to be used with any plane. The middle point of the lower border of each object’s 2D bounding box represents the point that it touches the ground (red $\star$ in Fig. 3).

Geometry-Based 3D Location Estimator performs 2 steps to estimate the 3D location of an object from its 2D bounding box. First, based on the second assumption, Geometry-Based 3D Location Estimator finds an equation that represents a Vector of Possible 3D Locations of an object. Second, based on the first and second assumptions, Geometry-Based 3D Location Estimator finds an Exact 3D Location from the vector that intersects with the ground.

Vector of Possible 3D Locations. Using Eq. 5, we convert any 2D point in the pixel coordinate system to a 3D point in the world coordinate system, if we know $z_{c}$. Since we do not know $z_{c}$ yet, we can derive a parametric equation representing all possible 3D points (red line in Fig. 3) converted from the 2D point. Let $d$ be the unknown distance of the object from the camera.

Exact 3D Location. We assume that the bottom line of the object’s bounding box touches the ground; therefore, $(x,y,z)$ also touches the ground. Because the ground is $z=0$ in our case, we can solve the Eq. 7 for $d$. Once we know $d$, we can solve the parametric Eq. 7 for $x$ and $y$ (blue $\star$ in Fig. 3).

Geometry-Based 3D Location Estimator relies on the assumptions mentioned, which do not always hold, especially, the first one. Nevertheless, Spatialyze can analyze users’ filter predicates and tell whether the types of objects of interest can be assumed to touch the ground, applying the optimization only then. For example, “car,” “bicycle,” or “human” touch the ground, while “traffic light” does not. In addition, Geometry-Based 3D Location Estimator is 192$\times$ faster compared than Monodepth2 on average. If one of the estimated 3D locations of an object in a video frame ends up being behind the camera, which means that the object does not touch the ground, Spatialyze can fall back to using Monodepth2 for that frame. Otherwise, Geometry-Based 3D Location Estimator provides 99.48% runtime reduction on average for object 3D location estimation and 52% for the video processing.

Suppose a car is visible to a Camera and driving in a lane. As discussed in § 4.1.1, a Movable Object of type “car” has 2 inherited physical behaviors: it follows the lane’s direction and travels at the speed limit regulated by traffic rules. At a particular frame, the Exit Frame Sampler leverages these behaviors to estimate the trajectory of the car so that the object tracker need not track any frame until: i) a car exits its current lane; ii) a car exits the Camera’s view; iii) a new car enters the Camera’s view. These events are sampleEvents. The Exit Frame Sampler samples the frame when a sampleEvent happens for the object tracker to track.

For (i), when the car is in a lane, without object tracking, the Exit Frame Sampler assumes that it follows the lane’s direction until it reaches the end of the lane. After it exits the lane, it may enter an intersection and stop traveling in a straight line. To maintain the accuracy of the trajectory, the object tracker needs to perform data association at the frame right before the car exits the lane. In contrast, if the car is already at an intersection, it may not travel in a straight line; therefore, the object tracker cannot skip any frame.

Event (ii) is the first frame that the car becomes invisible to the Camera. If this event happens before the car exits its lane, although its trajectory continues along the lane, the object tracker needs to perform data association at the frame before the car becomes invisible to the Camera as the end of the car’s trajectory.

For (iii), if a new car enters the camera’s view, the object tracker needs to start tracking the new car at that frame.

If a frame contains multiple cars, the Exit Frame Sampler skips to the earliest frame that (i), (ii), or (iii) is estimated to happen for any car, which prevents incorrect tracking for any of them. Our sampling algorithm implements this idea. Given a current frame and its detected cars, it samples the next frame for the object tracker to track. This algorithm starts from the first frame of a video to find the next frame, skips to it, and repeats until the end of the video.

Because the algorithm depends on the 2 mentioned inherited physical behaviors, it only works when users filter for Movable Objects with such behaviors, such as vehicles. Therefore, the video processor only adds the Exit Frame Sampler when users’ workflow Filters on the object type being vehicles.

3 shows the pseudocode of each sampleEvent. exitsLane implements (i) when the car exits the lane. Given the car’s location at the current frame (carLoc) and the lane that contains the car, we assume that the car drives in the lane straight along the lane’s direction. In line 2, we model the car’s movement as a motion tuple (carLoc, lane.direction). We compute the intersection between the car’s motion tuple and the lane as the location where the car exits the lane. Given the car’s speed v, we know the time it reaches the exit location starting from the current frame in line 3. We sample the frame before the car reaches the exit location. exitsCamera implements (ii) when the car exits the camera’s view. Knowing the car’s current location, moving direction, and speed, carMoves computes its location at any given frame in line 8. In line 7, we use the viewable area of the Camera at each frame derived from § 6.1 to find the first frame when the car’s location is not in the camera’s view. This is the frame when the car already exits the camera’s view, so we sample its preceding frame. newCar implements (iii) when a new car enters the Camera’s view. In line 12, we sample the next frame that has more cars detected than the current one. The number of cars is a good heuristic to predict that a new car is entering the frame.

At the current frame, the Exit Frame Sampler first finds the frame in which we have more detections for sampleEvent (iii). For each car, the Exit Frame Sampler samples frames for sampleEvents (i) and (ii). Among (i), (ii), (iii), the Exit Frame Sampler choose the earliest sampleEvent as the next frame for the object tracker to track.

To evaluate the efficacy of the Exit Frame Sampler, we define “skip distance” as the number of frames skipped between two non-skipped frames. We quantify tracking performance using the Exit Frame Sampler by summing the runtime of the sampling algorithm and StrongSORT from the current frame to the next non-skipped frame and dividing that by the runtime without running the Exit Frame Sampler. After processing all the videos from the nuScenes dataset, we computed the average for all data points with the same skip distance. As Fig. 4 shows, the runtime ratio decreases as the skip distance increases. With an average skip of 3.6 frames, per-frame runtime is 39% of the original.

Meanwhile, skipping too many frames results in the tracker losing sight of the target vehicles. To assess this risk, we computed the F1 score at each skip distance. The ground truth is the object trackings using StrongSORT without the Exit Frame Sampler. Here, “prediction” refers to whether an object at frame $f$ is correctly tracked at frame $(f+\textrm{skip distance})$ as predicted by the Exit Frame Sampler. Fig. 4 shows that the accuracy stays high for skip distances at 13 with the runtime of 28.27% of the original per frame. Hence, we set the maximum skip distance to 13 to maximize this accuracy vs runtime tradeoff. We omit the skip distances over 20 from the graph due to their poor accuracy to focus on effective metrics.

We compare the runtime of the Spatialyze pipeline with that of EVA’s implementation using the same queries. EVA is a VDBMS that allows custom user-defined functions (UDFs) along with their runtime optimizations. Since EVA executes the queries on a frame-by-frame basis, it cannot compute object tracks (and hence object directions), so we use EVA to evaluate only the object detection capability of Spatialyze with Q5-8. To use EVA’s caching mechanism, we execute the queries on EVA when they are run in series without resetting EVA and its database (running Q6 directly after Q5, Q7 directly after Q6, etc). The results are shown in Fig. 5. Our goal in comparing against EVA is to evaluate the efficiency of the two system’s query optimization techniques in § 6.1 and § 6.3.

As shown, Spatialyze performs 2-7.3$\times$ faster than EVA on Q5-7, since Spatialyze does not need to run Monodepth2 on each frame, due to the Object Type Pruner and Geometry-Based 3D Location Estimator. In addition, Spatialyze shaves even more time by employing the Road Visibility Pruner to avoid costly YOLO on frames where they are unnecessary. For Q8, our processing time is comparable to EVA. This is because Spatialyze’s Movable Objects Query Engine finds every possible triplet of cars; thus it performs 2 self-joins internally, while EVA only returns video frames with 3 cars or more. We also compare the lines of code (LoC) counts between Spatialyze (14-30) and EVA (58-60), showing that Spatialyze makes query implementation easier and requires less LoC for the same results.

We compare the run-time of the Spatialyze workflow with that of VIVA using the traffic application query from VIVA’s evaluation (Q9 in Table 1) as it is VIVA’s only query that involves geospatial content and road network. We run this query against both the VIVA-provided Jackson Square dataset as well as the nuScenes dataset. To match VIVA’s algorithm, we also resize Spatialyze’s input video to a resolution of $360\times 240$, resample the video at 1 FPS, and employ DeepSORT (Wojke et al., 2017) for tracking rather than StrongSORT to demonstrate Spatialyze’s extensibility. We notice that Spatialyze can execute the same workflow at the videos’ native resolution and FPS while VIVA crashes, which demonstrates Spatialyze’s ability to process large videos and the runtime efficiency of the video processor as a result of Spatialyze’s optimization.

Shown in Fig. 5, Spatialyze performs 1.68$\times$ faster compared to VIVA when run on VIVA’s dataset, and 6$\times$ faster when run on the nuScenes dataset. We attribute this increase in performance to Spatialyze’s Object Type Pruner which eliminates the amount of time spent tracking unnecessary objects. VIVA also spends significantly more time creating an optimization plan.

In addition, we compare the LoC of the implementations of VIVA (56) and Spatialyze (51), with Spatialyze providing a shorter implementation. While we do not have the ground truth to compare with, Spatialyze has higher accuracy in the query results: 45% of tracks returned by Spatialyze are indeed cars turning left. Meanwhile, only 35.7% of the tracks returned by VIVA are correct.

We compare the run-time of the Movable Objects Query Engine stage with the same queries implemented using the nuScenes Devkit (Caesar et al., 2019). NuScenes Devkit is a Python API used to query results from the nuScenes dataset (Caesar et al., 2019). We only compare the Movable Objects Query Engine stage as Devkit operates on already processed videos and ingested object annotations.

The Devkit implementation of Q4 ran out of memory during execution due to the creation of too many Python objects, as a result of materializing all possible combinations of 3 object tuples in memory before filtering them. Shown in Fig. 5, it also takes significantly longer to execute the same query as Spatialyze, with Spatialyze achieving a 117-716$\times$ faster runtime. Two of the main factors that allow Spatialyze to achieve this better execution time are the following. First, Spatialyze pre-processes the road network data, generating additional columns and indexes that allow it to avoid costly joins, which contribute greatly to the large execution time of Devkit. Second, certain Devkit functions perform costly linear algebra that is avoided by Spatialyze using the geospatial metadata store. Comparing the line counts between the different systems, it took 55-123 lines in Devkit to implement the queries while it only took 12-29 lines to do so in S-Flow.

We compare the run-time of the video processor of Spatialyze with that of OTIF on object tracking. We run each of the two systems on the sampled nuScenes datasets and compare the number of frames processed per second for each system. OTIF’s training is 61m37s. After it is trained, OTIF tracks objects at 17.3 FPS. For Spatialyze, our video processor applies all optimizations elaborated in § 6, and it processes videos at 18.3-39.5 FPS to get the tracks for each query. Without counting OTIF’s training time, Spatialyze still tracks objects faster.

SkyQuery is an aerial drone sensing platform for detecting and tracking vehicles from top-down videos. A user inputs an aerial drone’s video and its geospatial data, then constructs a query to detect and track objects. Spatialyze and SkyQuery both process geospatial videos by 1) detecting objects of interest, 2) finding the objects’ 3D locations, and then 3) tracking the objects.

To compare with SkyQuery, we implemented the 3 steps mentioned as Spatialyze’s video processing steps, and used SkyQuery’s customized YOLOv3 for car detection, their 3D location estimator, and SORT (Bewley et al., 2016) for object tracking. We retained the rest of Spatialyze’s components as well as the optimization steps. Then, we executed both of the systems on Q10 on SkyQuery’s video and geospatial metadata, and compared execution times. As shown in Fig. 5, Spatialyze processes 6.08 FPS, while SkyQuery processes 5.15 FPS, making us 18% faster. We write 15 lines of S-Flow vs 4 lines of SkyQuery to express Q10. The majority of the lines in S-Flow are spent on setting up the world and inputting videos and geospatial metadata. While we input videos and geospatial metadata into Spatialyze using S-Flow, we need to specify such input directories in the command line when starting SkyQuery.

As our evaluation uses the same ML models as SkyQuery, our speedup is entirely due to Spatialyze’s leveraging of the query’s semantics to prune video frames and avoid executing ML functions on them. Specifically, Spatialyze uses the Road Visibility Pruner to exclude video frames that do not contain any cycling lanes. We do not evaluate our accuracy in this evaluation as we use the same ML inference functions as those in SkyQuery. As the only optimization technique applied in this evaluation is the Road Visibility Pruner, it only prunes out video frames that do not contain a cycling lane, and thus, does not affect the query result.

The average runtime of our workflow execution without any optimization is 34 seconds for each video. When broken down, 0.01% of the time is spent in the Data Integrator; 89.9% in Video Processor; 9.5% in Movable Objects Query Engine; 0.6% in Output Composer. In this section, we evaluate the effect of each of our optimization techniques, by executing Spatialyze on the Q1-Q4. Because the video processing plans for Q3 and Q4 are the same, we do not discuss Q4 in this section.

With all optimization techniques, we achieve 2.5-5.3$\times$ speed up over the baseline plan, as shown in Fig. 5. The Road Visibility Pruner affects the entire plan. It prunes out 3.8% of the frames that do not contain “lane” in Q3 and 21.5% of the frames that do not contain “intersection” in Q1-2, with 3.2-20.0% runtime reduction. The Object Type Pruner only affects StrongSORT. It prunes out 36.5% of objects that are not cars in Q2-4 or trucks and 86.3% that are not pedestrians in Q1, with 7.0-26.3% runtime reduction. The Geometry-Based 3D Location Estimator makes the runtime portion of 3D location estimation insignificant (from 48% to 0.55%). Q1 does not execute the Exit Frame Sampler as it only works with cars or trucks. The Exit Frame Sampler has an overhead runtime of executing § 6.4.2; however, it reduces the number of frames into StrongSORT (13.1%), with 0.8% runtime reduction. We also evaluate the execution time with respect to video length by varying the video length input into the workflow. We found that the execution time of the workflow is linearly proportional to video length and Spatialyze can process videos larger than the available memory.

Our optimization techniques potentially reduce object tracking accuracy as a result of dropping frames. To quantify this, we evaluate our optimization techniques using the execution results from (SB) setup as the ground truth. Then, we compare the execution results from other setups against that of the (SB).

We evaluate our tracking accuracy of each experiment setup by comparing the tracking output from the experiment setup with the tracking output from (SB) setup, using HOTA (Luiten et al., 2020), an evaluation metric for measuring multi-object tracking accuracy. Using the ground truth tracks from a video and prediction tracks from the same video, HOTA returns an Association Accuracy (AssA) score. In this evaluation, the ground truth tracks are the tracking results from the (SB) setup, and the prediction tracks are the tracking results from each of the other setups. We also exclude object detections from the frame pruned by the Road Visibility Pruner because this pruning is a part of users’ predicates and will not be output.

In Fig. 5, the Road Visibility Pruner (S1) causes a small AssA drop of 0.4% for Q3-4 and 4.7% for Q1-2. The Object Type Pruner (S2) also causes a small AssA drop of 2.5% from Q2-4 and 5.3% for Q1. We do not include (S3) into the results since the object tracker only concerns the 2D bounding boxes of objects; Geometry-Based 3D Location Estimator does not affect the AssA of the object tracker. With all 3 optimization techniques (S5), the video processor still produces accurate object tracks of 93.4% on average compared to (SB), while speeding up 2.5-5.3$\times$ of its runtime. With all optimization techniques (S6), the video processor’s accuracy for object tracking is 84.5% on average, while speeding up 1.65-4.32%, additionally.