Topo-boundary: A Benchmark Dataset on Topological Road-boundary Detection Using Aerial Images for Autonomous Driving

Road-boundary detection is important for autonomous driving. It can be used to constrain autonomous vehicles running on road areas to ensure driving safety. Compared with online road-boundary detection using on-vehicle cameras/Lidars, offline detection using aerial images could alleviate the severe occlusion issue. Moreover, the offline detection results can be directly employed to annotate high-definition (HD) maps. In recent years, deep-learning technologies have been used in offline detection. But there still lacks a publicly available dataset for this task, which hinders the research progress in this area. So in this paper, we propose a new benchmark dataset, named \textit{Topo-boundary}, for offline topological road-boundary detection. The dataset contains 25,295 $1000\times1000$-sized 4-channel aerial images. Each image is provided with 8 training labels for different sub-tasks. We also design a new entropy-based metric for connectivity evaluation, which could better handle noises or outliers. We implement and evaluate 3 segmentation-based baselines and 5 graph-based baselines using the dataset. We also propose a new imitation-learning-based baseline which is enhanced from our previous work. The superiority of our enhancement is demonstrated from the comparison. The dataset and our-implemented code for the baselines are available at \texttt{\url{https://tonyxuqaq.github.io/Topo-boundary/}}.

I. INTRODUCTION
R OAD boundary refers to the dividing line between the road area and off-road area. It can be used to constrain self-driving cars running on road areas, which is important to the safety of autonomous driving. Currently, most existing works rely on vehicle-mounted sensors (e.g., cameras or Lidars) [1]- [4] for online road-boundary detection. However, online detection could be severely degraded by occlusions, which is very common in real road environments. Moreover, online detection could be restricted by limited computing resources on vehicles, especially for deep-learning models that require GPU. To relieve the aforementioned issues, some works resort to detecting road boundary (or its analogies, such as lane or curb) offline using bird-eye-view (BEV) point-cloud maps or aerial images. As the results are presented in BEV images, they can also be directly utilized for annotating high-definition (HD) maps. So we detect road boundaries offline in this paper. Moreover, our detection results are presented in the form of topological graphs (i.e., vertices and edges). This is important because besides pixel-level annotations, the topological graphs can also identify road-boundary instances and find the spatial connection information of the boundaries.
The published literature working on topological roadboundary detection is very limited. Most of existing works focus on the analogy problem: line-shaped object detection, such as road-lane, road-curb and road-network detection [5]- [11]. They can be generally divided into two categories: segmentationbased solutions and graph-based solutions. A typical pipeline of the former is first using semantic segmentation to get rough detection results, and then performing heuristic post-processing algorithms on the segmentation maps to refine the results. The latter directly finds the graph structure for the line-shaped objects through iterative graph growing. With the great advancement of artificial intelligence, deep-learning technologies are adopted by current existing methods, and great superiority over traditional algorithms is achieved. However, deep-learningbased methods require large-scale datasets to train a model. To the best of our knowledge, there is still no publicly available datasets for road-boundary detection in BEV images, which hinders the research process in this area. This motivates us to build a large-scale benchmark dataset, named Topo-boundary, for road-boundary detection.
Our dataset is derived from the NYC Planimetric Database [12]. The raw geographic data (a large whole map, see Fig.  1) in the NYC Planimetric Database covers the whole New York City, including 2,147 5000 × 5000-sized 4-channel (i.e., red, green, blue and an infrared channel) aerial image tiles (i.e., small squared aerial image constituting the large whole map) and a set of polylines as the road-boundary ground-truth label. To build our Topo-boundary, we convert the polyline label to graph (i.e., vertices and edges) and split every tile into 25 smaller 1000 × 1000-sized patches. After removing patches with inappropriate annotations, such as patches without road boundaries, 25,295 patches remain. Each patch consists of a 4-channel image and 8 labels for different sub-tasks, such as binary semantic segmentation, orientation learning [6], etc. The dataset can be used for both segmentation-based solutions and graph-based solutions for road-boundary detection.
To facilitate future research on road-boundary detection, we implement and evaluate multiple baselines, including 3 segmentation-based baselines, 5 graph-based baselines. We also . Each patch (P ) contains a 4-channel 1000 × 1000-sized aerial image I and ground-truth road boundaries G gt . The G gt in the figure is annotated by polylines, of which edges and vertices are denoted by cyan lines and yellow points, respectively. Based on G gt , we generate 8 types of ground-truth labels for different tasks. The filtering step is to remove patches based on pre-defined rules. After filtering, 25,295 patches finally remain in our Topo-boundary. For better visualization, only RGB channels of the patch image are visualized. Moreover, the width of the ground-truth polylines is increased (the actual width is one pixel). This figure is best viewed in color.
design and compare a new imitation-learning-based baseline which is enhanced from our previous work iCurb [11]. For all the baselines, the input is a 4-channel aerial image, the output is the graph representing road boundaries. Our implemented code for these baselines are open-sourced along with our dataset.
As line-shaped objects are usually long, thin and irregular, only using pixel-level metrics is not sufficient to evaluate the performance of a method. In past works, average path length similarity (APLS) has been widely used to evaluate topology correctness [13]. But since in most cases road boundaries are simple polylines without branches, APLS suffers from randomness and inefficiency. Inspired by the naive connectivity metric proposed in [14], we design a new entropy-based connectivity metric (ECM) to evaluate the connectivity of the obtained roadboundary graph, which is effective and more efficient. We summarize our contributions here: 1) We release the Topo-boundary benchmark dataset for topological road-boundary detection using aerial images.
To the best of our knowledge, this is the first publicly available dataset for this task. 2) We propose new evaluation metrics for the task, including relaxed pixel-level metrics and a new entropy-based connectivity metric. 3) We quantitatively evaluate 9 baseline models using the proposed dataset, which could facilitate comparative study for future methods. 4) We open-source our-implemented code for the baselines.
The code can also be modified with a little effort for other line-shaped object detection.

II. RELATED WORKS A. Segmentation-based line-shaped object detection
There are very few segmentation-based works directly detecting road boundaries topologically. So we review several line-shaped object detection works [5], [6], [15]. Volodymyr et al. [15] proposed the first deep-learning model with iterative refinement for road-network detection using aerial images. Their solution was further improved by Anil et al. [6], in which the authors not only proposed better networks and a training scheme, but also utilized the orientation map to enhance the semantic segmentation results. Different from the above papers using iterative refinement, the solution proposed by Mattyus et al. [5] first put forward connection candidates to correct disconnections, and then trained another network to filter candidates. Although segmentation-based solutions are efficient to carry out, they can only produce results at the pixel-level. Moreover, they were often implemented with multi-stage pipelines, so they could not be optimized as a whole, making the graph sensitive to incorrect topology.

B. Graph-based line-shaped object detection
Taken images as input, graph-based methods can directly output the graph representing target objects. Iterative graph growing is the most commonly used technique, which generates vertices along with the line-shaped object starting from an initial vertex. Past works focusing on other line-shaped objects are similar to our task, such as road-lane detection [9], [16], roadnetwork detection [7], [8], [17] and road-curb detection [11]. RoadTracer [7] is believed to be the first work in this category. In [7], the authors trained a multi-layer CNN and successfully extracted the graph of very large road networks. Liang et al. [14] directly worked on road-boundary detection in the BEV point-cloud map. They facilitated semantic segmentation by direction map prediction and proposed cSnake for iterative graph growing. To better solve the graph growing task, lineshaped object detection was first analyzed from the perspective of imitation learning in our previous work iCurb [11]. iCurb presented superiority over other works on road curb detection owing to the training strategy and graph growing policy.

C. Evaluation metrics for topological correctness
In the past works on road network detection, topological correctness was usually measured by shortest-path-based metrics, such as APLS [13] and too long/too short (TLTS) similarity [18]. However, due to the random sampling process, these metrics suffer from inefficiency and randomness. Alternatively, in [14], a naive metric measuring the connectivity of road boundaries was proposed, but it is too sensitive to noises and may cause incorrect evaluation results. iCurb modified the naive metric and addressed the problem to some extent. However, incorrect evaluation still happens. So in this work, we make further revisions to this metric and propose an entropy-based metric for connectivity evaluation.

D. Datasets for line-shaped object detection
To the best of our knowledge, [14] is the only published work on road-boundary detection using BEV images. In [14], a dataset was created, which contained BEV point-cloud images, RGB images and elevation gradient images. But unfortunately, the dataset was not publicly available. In the road-network detection area, the data was obtained from commercial geospatial datasets [13] or by processing raw geographic images collected from public platforms [19]. Although these datasets are publicly available, due to the topological differences between road networks and road boundaries, they could not be used in our task.

III. THE PROPOSED DATASET
To create our Topo-boundary dataset, we generate images and ground-truth labels from the raw geographic data provided by the NYC Planimetric Database [12]. The WGS84 coordinate system is used in [12], while in our Topo-boundary, all the coordinates are transformed to the image coordinate system to facilitate research in this area. Fig. 1 shows the processing pipeline to create our Topo-boundary. We first split large data tiles into patches, then generate ground-truth labels for each patch, and finally remove inappropriate patches according to predefined rules.

A. Splitting data tiles into patches
The raw geographic data covers the whole area of the New York City, including 2,147 data tiles. Each tile (T ) is a 5000 × 5000-sized image with road-boundary ground-truth label. Each pixel represents 1 feet (around 15.2cm). We split each tile into 25 smaller patches (T = {P i } 25 i=1 ) to reduce the GPU memory cost during training. Since our task is mainly performed at the patch level, the subscript i is removed from P i for expression conciseness in the following text. Each patch (P ) contains a 4channel (red, green, blue, infrared, the infrared channel is more sensitive to vegetation and soil) 1000 × 1000-sized aerial image I and ground-truth road boundaries G gt . We use G gt to generate 8 labels for different sub-tasks.
The raw ground-truth label for road boundaries is the PAVEMENT_EDGE feature from the NYC Planimetric Database. PAVEMENT_EDGE is manually annotated in the form of polylines (a kind of graph without branches), of which the vertices and edges are recorded using the WGS84 coordinate system. The polylines cover road-surface edges, airport runways and alleys. From the whole map PAVEMENT_EDGE, we obtain the ground-truth road boundary G gt for each patch P .
Unlike tile images, PAVEMENT_EDGE cannot be directly cut and split because: (1) some edges e = (v a , v b ) may have one vertex v a in a patch while the other vertex v b in another patch; (2) some road boundaries may be cut into multiple pieces by different patches. For the former, we replace the vertex outside the patch (i.e., v b ) with the intersection point of e and the patch edge. For the latter, we split the corresponding road boundaries into multiple instances and update PAVEMENT_EDGE.
After processing PAVEMENT_EDGE, for each patch, the ground-truth road boundary is still a set of polylines where V i and E i are the set of vertices and edges in G i gt , respectively. Vertices V i are recorded in a list, and then edges in a graph can be easily obtained by connecting two neighboring vertices in the list, thus the edge set E i is omitted. Note that G i gt is sparsely distributed (i.e., adjacent vertices are not eight-neighboring to each other in the image coordinate system).

B. Generating ground-truth labels for each patch
For each patch, we generate 8 different types of labels for different tasks. The labels are: annotation sequence S A , dense sequence S D , binary map M B , instance map M I , endpoint map M E , inverse-distance map M ID , direction map M D and orientation map M O . All the label maps are generated from ground-truth road boundaries (G gt ) within the current patch by our processing algorithms, and are recorded in the image coordinate system of the current patch. 1) Annotation sequence and dense sequence: As the groundtruth road boundaries are annotated vertex-by-vertex as chain sequences, the vertices of a road boundary instance G i gt are ordered starting from an initial vertex to the end vertex. We call the ordered vertices of G i gt as the annotation sequence S A . S A is critical to generate other labels and can be applied to train graph-based solutions. However, graph-based solutions trained by S A suffer from the teacher forcing problem [20], which is caused by the data distribution mismatch between the training and inference period. It is also analyzed in [7]. To address this problem, the training label for iterative graph generation should be generated on-the-fly. Therefore, S A needs to be densified. For every two adjacent vertices in S A , interpolation is conducted to obtain the dense sequence S D . In S D , any two adjacent vertices are eight-neighboring to each other. The densification process is illustrated in Fig. 3.
2) Binary map, instance map and endpoint map: Binary map M B is commonly used for semantic segmentation. The dense sequence S D can be directly used to generate M B by setting all the pixels covered by S D as 1 (i.e., foreground pixels) and the other pixels as 0 (i.e., background pixels). In this way, we can get the binary map of a patch and its topological correctness can be guaranteed. The instance map M I can be obtained similarly, but pixels covered by different instances are multiplied with instance IDs.
To facilitate segmentation and generate candidate initial vertices for iterative graph generation, endpoint prediction is required in some solutions [11], [14]. For each road boundary instance G i gt in a patch, there are 2 endpoints. We multiply each endpoint by a Gaussian kernel function.
3) Inverse-distance map and direction map: Inverse-distance map (M ID ) prediction is first proposed in [21] to facilitate semantic segmentation. The value of each pixel in this map is the reciprocal of its shortest distance to the ground-truth road boundary. Compared with the binary map M B , M ID is more informative considering that all the pixels of M ID are encoded with information. The generation of M ID is accelerated by GPU parallelism in our implementation.
To further make use of the spatial information in M ID , the authors in [14] generate the direction map M D based on M ID . The direction map is a vector field (M D ∈ R 2×H×W ) of normal directions to the road boundary. It is calculated by For these patches, few methods can obtain reasonable results, especially for graph-based methods. Therefore they are removed at this stage. For better visualization, only RGB channels of the patch image are visualized, and the width of the ground-truth polylines is increased (the actual width is one pixel).
taking the Sobel derivative of M ID followed by a normalization step. Intuitively, M D records the direction to the closest road boundary of each pixel by unit vectors. The application of M D and M ID encourages the neural network to focus on road boundaries. 4) Orientation map: Orientation learning [6] makes use of the direction and connection information of road networks, which greatly enhances the performance of semantic segmentation. Thus we provide the orientation map for this task to assist road-boundary detection. Due to the bi-direction nature of road boundaries, we regard them as undirected graphs. For each road boundary instance G i gt , we randomly select one end vertex as the starting point while the other as the ending point. Then from the starting point, for every two adjacent vertices, we calculate a directional vector and convert it to a radian value r. For all pixels covered by the edge connecting these two adjacent vertices, their values are set to r. Intuitively, the value of each foreground pixel is the radian value of the edge it belongs to. Fig. 2 displays all the label maps for a sample patch.

C. Removing patches according to pre-defined rules
We remove the inappropriate patches according to the following predefined rules: 1) The patch with no road boundary inside. Such a case is quite common, especially in suburb area images; 2) The patch with intersection points. In the raw ground-truth label of the road boundary, some alleys are snapped to it and cause intersections, which is not appropriate. Thus we remove these patches; 3) The patch that has very complex scenarios, such as overlapping interchanges. The cases in the removed patches would happen in city-scale real-world applications. So, this could be treated as a limitation of our work at this stage. Fig. 4 shows sample inappropriate patches.

D. Data splitting
After filtering, there are finally 25,295 patches remaining in our Topo-boundary. We randomly split these patches into a training set (10,236 patches), a validation set (1,770 patches), a testing set (3,289 patches) and a pretraining set (10,000 patches). The pretraining set is used for multi-stage methods, like [5], or to pretrain the feature extraction module of the graph-based solutions to accelerate the training convergence, such as [9]. If pretraining is not needed, the samples in this set could be used for training. The boroughs of New York City (e.g., Queens or Manhattan) is not considered during data splitting. The above data splitting scheme is adopted in the experiments of this paper. Users are free to split the dataset according to their needs.

IV. EVALUATION METRICS
To ensure comprehensive and fair comparison, we design our evaluation metrics, including 3 relaxed pixel-level metrics (i.e., Precision, Recall and F1-score), the naive connectivity metric [14], APLS [13] and an entropy-based connectivity metric (ECM) for topological correctness measurement. For all the metrics, larger values indicate better performance.

A. Pixel-level metrics
Pixel-level metrics (i.e., Precision, Recall and F1-score) measure the prediction accuracy of every pixel. Unlike most past works that directly compare the prediction results with the ground truth, in this work we use the relaxed version of these metrics following [9], [11], [14].
Let G pre denote the predicted graph and G gt denote the ground-truth graph. Note that both graphs have been densified. Precision is the ratio of pixels in G pre that fall within τ distance to G gt . Recall is the ratio of pixels in G gt that fall within τ distance to G pre . Distance τ reflects the tolerance of inaccuracy. If τ = 1, the relaxed pixel-level metrics degenerate into the commonly-used hard pixel-level metrics. In this paper, we report the evaluation results with τ as 2, 5 and 10 pixels, respectively.

B. The proposed entropy-based connectivity metric (ECM)
Assume the predicted road boundary instances are G pre = {G j pre } M j=1 and the ground-truth instances are G gt = {G i gt } N i=1 . In our task, topology errors mainly refer to disconnections. Therefore, the topology correctness metric should suffice the following principles: (1) Punish incorrect disconnections; (2) Assign shorter ground-truth instances G i gt less weights; (3) Longer incorrect disconnection receives a larger penalty; (4) The prediction whose dominant G j pre has higher dominance should receive a higher score. Dominant predicted instance G j pre is the instance with the highest dominance value, where dominance value is the ratio of the length of G j pre to the sum of the length of predicted instances assigned to G i gt . Among metrics used in the past work, the widely applied path-based metrics, like APLS and TLTS, meet almost all aforementioned requirements. However, they suffer from randomness and inefficiency due to the random sampling process. Because of this, in [14], an alternative naive connectivity metric is proposed. The authors first match instances in G pre with instances in G gt by minimizing the Hausdorff distance [22]. If an instance (c) has more disconnections, thus the connectivity score of (b) should be larger than that of (c). All three metrics meet the requirement. Similarly, (b)(d), (b)(e), (b)(f) reflect whether metrics suffice principle 2,3 and 4, respectively. From the comparison, we find that both APLS and ECM work well for all cases, while the naive connectivity metric and pixel-level metrics fail to follow the principles. Please zoom in for details.
G j pre matches with G i gt , G j pre is assigned to G i gt . For each ground-truth instance G i gt , let M i denote the number of assigned predicted instances. Then the connectivity of instance G i gt is C i = 1(Mi>0)

Mi
, and the final connectivity of the whole patch is the average sum of C i of all ground-truth instances.
This naive metric can reflect the connectivity of the prediction to some extent, but it fails to meet most aforementioned principles. To relieve this problem, in our previous work iCurb [11], we made some adjustments to the naive metric. The matching method is changed to a voting scheme. Each pixel of G j pre finds its Euclidean-closest G i gt and makes a vote, then G j pre is assigned to the ground-truth instance G i gt that wins the most votes. This voting scheme is more stable than the Hausdorff distance that is sensitive to noises. In addition, a weighting hyper-parameter that gives the longer G i gt larger weights is assigned to each G i gt . However, the connectivity metric from the iCurb paper cannot meet all the requirements. Therefore, in this paper, we further modify the connectivity metric and propose an entropy-based connectivity metric (ECM), which is shown in the following equation: where C i is the connectivity of the i − th ground-truth instance G i gt ; α i is the completion of G i gt , which is equal to the sum of the length of assigned instances in G pre projected onto G i gt divided by the length of G i gt ; N is the total number of G i gt in the current patch; M i is the number of predicted road boundary instances G j pre that are assigned to G i gt , and p j is the dominance of G j pre . Entropy is a definition created by Shannon in information theory to measure information content. An event with greater uncertainty tends to have larger entropy. If the dominant predicted instance G j0 pre has large dominance value, G i gt should have good connectivity measure C i since G j0 pre can well approximate G i gt with more certainty. In summary, ECM assigns longer predicted graph instances with larger weights to calculate C i , so that short instance could not greatly affect the final evaluation results. Therefore, ECM shows better ability to handle noises and outliers. An example comparing different connectivity metrics is shown in Fig. 5.

V. BASELINE MODELS
In this work, we implement several segmentation-based baselines and graph-based baselines. We also design a new imitationlearning-based method which is enhanced from our previous work iCurb [11].
A. Segmentation-based baselines 1) Naive baseline: This baseline is proposed by ourselves. Firstly, we employ U-net [23] to obtain the segmentation map of road boundaries. Then, the segmentation results are refined by filtering noisy segments. Finally, the refined segmentation map is skeletonized to get the graph for the road boundaries.
2) DeepRoadMapper: This baseline (ICCV2017) [5] proposes to fix disconnections in road network predictions. Due to the similarity between our task and road network detection, we adapt their method for road-boundary detection.
3) OrientationRefine: This baseline (CVPR2019) [6] utilizes the orientation map to enhance the segmentation of road networks and achieves improvements. Besides, an extra network is trained to refine the segmentation results iteratively. This work can be directly used for our task without many modifications.
B. Graph-based baselines 1) RoadTracer: This baseline (CVPR2018) [7] is believed to be the first work that solves the line-shaped object detection problem by an iterative graph generation approach. However, the network for feature extraction is merely a multi-layer CNN without skip connections.
2) VecRoad: This baseline (CVPR2020) [8] greatly improves RoadTracer, but follows the same core idea. Res2Net [24] is utilized as the backbone for multi-scale feature extraction. However, there is a limited improvement to the training strategy. Both VecRoad and RoadTracer work on road network detection, which has different topological characteristics with the road boundary (i.e., road boundaries are scattered polylines without branches while the road network is a connected graph with many intersections), thus we modified their exploration algorithm and the overall pipeline to make them applicable for our task. Besides, road network detection only requires coarse detection of the road centerline, while road boundary detection expects the fine structure of both sides of the road. Therefore, our task has higher demands compared with road network detection.
3) ConvBoundary: This baseline (CVPR2019) [14] is the only graph-based work that directly focuses on road-boundary detection. It is a two-stage solution. First, it predicts the inversedistance map, endpoint map and direction map simultaneously. Then, based on these three maps, a model named cSnake is trained to generate the final graph vertex-by-vertex.

4) DagMapper:
This baseline (ICCV2019) [9] is designed for road-lane detection. The input of both DagMapper and ConvBoundary are BEV images of pre-built point-cloud map. Compared with aerial images, BEV images of point-cloud map has much higher resolution and simpler scenarios. For example, the occlusion issue in the point-cloud map is relieved and only the near-road area is covered, which could be regarded as a kind of attention. However, the point-cloud map is time-consuming and expensive to obtain and update, while aerial images are more and more publicly available all over the world. Therefore, our task is more suitable for wide-area applications. 5) iCurb: This baseline (RAL2021) [11] is the first work that solves the iterative graph generation from the perspective of imitation learning. iCurb has a DAgger-based [25] training strategy, which greatly enhances the performance. This work focuses on road-curb detection, which is a subclass of road boundary, thus it can be directly applied to our task.
Except RoadTracer, the code of all the graph-based baselines are not publicly available. So we implement them by ourselves.

C. The Proposed imitation-learning-based baseline
We propose a new imitation-learning-based solution based on our previous work iCurb [11], and the new solution is named as enhanced-iCurb. To the best of our knowledge, iCurb is the first work to solve the line-shaped object detection from the perspective of imitation learning. In [11], a DAgger-based solution is proposed. For each patch, the solution runs a round of restricted exploration as well as N rounds of free exploration, and aggregates the training dataset using the generated samples. Let π * denote the expert policy andπ denote the learner policy. The task is to learn theπ to mimic π * . Letv t and v * t respectively denote the actions produced byπ and π * at time t. During the sampling period, v t is used to denote the vertex to update the graph.
With the obtained predictionv t , we set the closest pixel of the ground-truth road boundary tov t as the label v * t to train iCurb. This algorithm generates the label on-the-fly and can ensure iCurb not be affected by the teacher-forcing problem. However, v * t heavily relies onv t and does not have a unique value, thuŝ π may make unpredictable actions and may converge to a suboptimal policy. In our experiments, for example, we find that the edge length of the road boundary predicted by iCurb is almost random sometimes. It requires careful parameter tuning to prevent this. To make the training process more stable and predictable, the orientation map M O is leveraged to calculate v * (a) GT (b) Naive (c) [5] (d) [6] (e) [7] (f) [8] (g) [14] (h) [9] (i) [11] (j) Ours

A. Experimental setup
We conduct experiments on a PC with an i7-8700K CPU, an NVIDIA GTX1080Ti GPU, and an RTX3090 GPU. The checkpoint with the best performance on the validation set is selected for inference. To measure the efficiency, we record the training time cost as well as the inference time cost of each baseline, and report their average time cost on each patch. For graph-based baselines, the ground-truth initial vertices added with Gaussian noise are used to start the iterative graph generation process. Considering the trade-off between efficiency and effectiveness, the number of rounds of the free exploration for both iCurb and enhanced-iCurb is set to 1.

B. Evaluation results
The comparative results are shown in Tab. I. Some qualitative demonstrations are shown in Fig. 6. The average processing time for efficiency evaluation is reported in Tab. II. As segmentationbased baselines directly optimize on pixel values, they tend to present good F1-scores, even the naive baseline. Segmentationbased baselines take relatively less time than graph-based baselines for training since they do not require an iterative process. However, these baselines do not have satisfactory performance on connectivity, because the spatial information of the patch image cannot be fully leveraged. Compared with the Naive Baseline, DeepRoadMapper can propose candidate connections to correct some disconnection and enhance the connectivity to some extent. But it is still restricted by the accuracy of the semantic segmentation. Once the segmentation network gives poor results, DeepRoadMapper cannot effectively improve the final performance. Moreover, generating correction candidates increases the time cost. OrientationRefine iteratively refines the obtained segmentation map in pixel-level with an extra network, which can obtain more concise correction results. Thus OrientationRefine achieves good connectivity and outperforms all the other methods on F1-Score. Instead of working on pixels, graph-based baselines generate the graph of road boundaries directly. Thus, they perform well on connectivity. However, due to the sequential process for graph generation, this kind of methods exhibit relatively lower pixel-level accuracy when the patch image has complicated scenarios. The training process of RoadTracer is fast since it is a small network. But the performance is inferior to others. VecRoad follows the similar idea of RoadTracer but the network backbone is replaced with a more powerful one, so its performance is improved but the training efficiency is degraded. Even though ConvBoundary and DagMapper present good results with point-cloud maps on their original tasks, they do not present satisfactory performance on this task (i.e., road-boundary detection using aerial images). iCurb provides a solution to this task using imitation learning. It gives better F1-Score and connectivity thanks to the DAgger-based training strategy. Enhanced-iCurb utilizes different algorithms to generate the training label and update the graph, which is more stable and predictable. It has good performance on all metrics and qualitative visualizations, thus the superiority of our new proposed method is demonstrated.

VII. CONCLUSIONS AND FUTURE WORK
In this paper, we proposed a publicly available benchmark dataset named Topo-boundary for topological road-boundary detection using BEV aerial images. Topo-boundary has 25,295 patches. Each patch consists of a 4-channel aerial image and 8 labels for different deep-learning tasks. We also designed a new metric for better connectivity evaluation. It was employed to compare 9 baselines together with some metrics used in the past works. The dataset and our implemented code for the baselines were publicly available on our project page. In the future, we plan to assign the prediction difficulty scores (i.e., smaller values for easy cases, and larger values for hard cases) to further label the dataset, so that the networks can be trained to be well adapted to various scenarios. Moreover, the patches removed in this paper will be considered for real-world applications.


extfieldsofstudy:
Medicine
Computer Science

text:
Find Outliers of Image Edge Consistency by Weighted Local Linear Regression with Equality Constraints †

In this paper, we propose a general method to detect outliers from contaminated estimates of various image estimation applications. The method does not require any prior knowledge about the purpose, theory or hardware of the application but simply relies on the law of edge consistency between sources and estimates. The method is termed as ALRe (anchored linear residual) because it is based on the residual of weighted local linear regression with an equality constraint exerted on the measured pixel. Given a pair of source and contaminated estimate, ALRe offers per-pixel outlier likelihoods, which can be used to compose the data weights of post-refinement algorithms, improving the quality of refined estimate. ALRe has the features of asymmetry, no false positive and linear complexity. Its effectiveness is verified on four applications, four post-refinement algorithms and three datasets. It demonstrates that, with the help of ALRe, refined estimates are better in the aspects of both quality and edge consistency. The results are even comparable to model-based and hardware-based methods. Accuracy comparison on synthetic images shows that ALRe could detect outliers reliably. It is as effective as the mainstream weighted median filter at spike detection and is significantly better at bad region detection.

Introduction
Edge consistency is crucial in many image processing applications producing perpixel estimates based on source images, such as depth estimation, object segmentation and alpha matting. Although these applications have very different models and purposes, the estimates are all expected to have consistent edges with the sources.
Edge consistency has a popular description known as "output image has an edge only if input image has an edge".The meaning of this description is twofold. Firstly, it means "estimate should be smooth if the source is smooth".Secondly, it means "estimate could be smooth whether the source has an edge or not".It is reasonable since most estimation processes are not single mappings. Pixels with different values might be the same after mapping. Therefore, the source and estimate have different status in the context of edge consistency.
Although the estimates are expected to fulfill edge consistency, it is not usually the case due to noises and outliers. Various algorithms have been proposed for noise suppression including global optimizations [1][2][3] and local filters [4,5]; however, outliers are less handled in the context of images [6][7][8][9].
Noises are derived from sensors and environments, leading to small biases which can usually be well described by statistical models. Outliers are caused by unexpected samples or improper designs of processing methods (termed artifacts in this situation). They might trigger large offsets and have very different forms between applications. Therefore, outliers are hard to model and suppress in a general way. Options on the table are limited: 1.
Ignore and treat them as noises; 3.
Median filter and its improved versions are good at removing small outlier regions such as spikes [11][12][13]. However, outliers might occupy large regions and happen to be the medians. Noise suppression methods are usually not aggressive enough to remove outliers, leaving artifacts such as halo-effect. In some applications, outlier detection methods are specifically designed based on prior, model or hardware. These methods are effective but not general. In most cases, we do not have a satisfactory option.
In this paper, we show that edge consistency itself is a valuable and under-exploited clue for general outlier detection. A hypothesize-and-verify algorithm termed ALRe (anchored linear residual) is proposed to find pixels undermining edge consistency. It offers per-pixel outlier likelihoods of estimates based on the source. The likelihoods can be transformed into inlier fidelities and then used as data weights of various post-refinement algorithms, producing better refined estimates. The algorithm requires no prior knowledge about applications or estimation method and has the complexity linear to pixel number. To the best of our knowledge, ALRe is the first general outlier detection method based on edge consistency. A preliminary version of ALRe is published in ECCV 2020 [14]. In this paper, we provide the full feature analysis and quantitative results on various applications, and compare its detection accuracy with the mainstream weighted median filter.
The rest of this paper is organized as follows. Section 2 introduces post-refinement algorithms and several limited outlier detection methods. Section 3 presents the details of ALRe. Section 4 analyzes its advantages and compares some other options. Section 5 gives examples. In Section 6, the value of ALRe as an add-on of post-refinements is investigated. Furthermore, its accuracy is tested on synthetic images. Conclusion is given in Section 7.

Related Works
Although corresponding outlier detection method is absent, edge consistency has been considered in various algorithms, such as WLS (weighted least squares) [2], JBF (joint bilateral filter) [4], GF (guided filter) [5] and WMF (weighted median filter) [11]. Note that these algorithms have multiple usages. The following introduction only includes post-refinement for image estimation. In this situation, they pursue a refined estimate q, which has similar intensities with the contaminated estimate p and consistent edges with the source I.

Weighted Least Squares
WLS [2] has a straightforward definition following the concept of edge consistency closely. It finds the optimal q minimizing the energy function where i is pixel index, J is the set of adjacent pixels, and λ balances the two terms. Smooth weight a ij is inversely correlated with the distance between I i and I j . WLS are continuously improved, such as efficient semi-global WLS [15] and constrained WLS [16], to keep pace with its applications. However, the data weight w i correlated with the fidelity of p i is usually undefined.

Joint Bilateral Filter
JBF [4] produces q by smoothing p based on I, as where x is the vector of pixel coordinate, Z i is normalizing parameter, and Ω i is the local region centered at pixel i. There are two kinds of weights including distance weight s and color weight c. The parameters σ s and σ c adjust the sensitivities of the spatial and color similarities, respectively. Bilateral filter have many other variants with similar structures, such as guided bilateral filter [17] and optimally weighted bilateral filter [18]. However, the data weight w j is usually undefined.

Guided Filter
GF [5] assumes local linear relationship between q and I and then solves the optimal q closest to p. It is defined as where a and b are linear parameters, suppresses large a for smoothness, and |Ω| means the pixel number of Ω. GF has been improved into many versions. Anisotropic guided filter [19] contains the weight w a ik , and weighted guided filter [20] contains w w k . Dai et al. [21] relaxed local support region Ω to the entire image domain and introduces the weight w t jk based on minimum spanning tree. Additionally, a kind of bidirectional guided filter can be found in [22]. These methods introduce various benefits, such as stronger edge-preserving behavior and less halo-effect. However, to take advantage of pixel fidelities, another kind of weight w j is required. It is not originally included in [5] but can be easily implemented without increasing complexity.

Weighted Median Filter
WMF [11] produces q by picking values from p. It is robust to outliers because unpicked pixels have no impact on the result. WMF is defined as where δ(x) is 1 if x equals 0, and is 0 otherwise. The weight w i,j depends on I i and I j (in this paper, it is produced based on the kernel of guided filter). Median filter has been improved in both robustness [12] and efficiency [13]. However, they might fail when filter size is large or some outliers happen to be the medians. This problem can be improved if the fidelity of each single pixel is available. It requires the weight denoted as w j . It is not originally included in [11] but can be easily implemented without increasing complexity.

Outlier Detection
In the field of haze removal, Fattal [23] proposed color-line model and Berman et al. [24] proposed haze-line model. Outliers in their initial estimates are detected based on the variances of fitted color-lines and the effective lengths of collected haze-lines, respectively. WLS is employed for post-refinement, and the data weight w is provided based on the detection results. It introduces robustness since pixels not following their models affect the final estimates little. However, these detection methods are only applicable to corresponding models and thus cannot be generalized to other models and applications.
In the field of disparity estimation, outliers can be robustly detected by cross check [25]. Pixels having different estimates between left-to-right and right-to-left matchings are considered as outliers, and their weights are set to zeros. JBF is employed for post-refinement, whose data weight w is provided based on the detection results. Despite the robustness, cross-check is also not generalizable because it requires multiple source images captured by specific hardware.
More often, outlier detection method is absent, and the post-refinement algorithms are used without data weights. In this case, outliers are treated as noises and not well removed. However, most of them are obviously in the view of edge consistency. In this paper, we propose ALRe to realize this simple, general and effective check.

Intuition
ALRe is based on the fact that estimate p and source I satisfy edge consistency if local linear relationship is established between them. Denote the local region centered at k by Ω k ; the local linear assumption is satisfied if where (a k , b k ) are linear parameters. It implies edge consistency because On the other hand, edge consistency does not always imply local linear relationship, especially when I Ω k has notably more edges than p Ω k . However, with proper mask size, Ω k contains few edges and colors; thus, the assumption is reasonable enough in most cases. Linear regression can be used in each Ω k to approach Equation (5) as much as possible. Based on the relationship between local linear assumption and edge consistency, the smaller the residual, the better the consistency. However, simply adopting linear regression has two problems: 1.
The residual of linear regression indicates the degree of edge consistency in Ω k , rather than the fidelity of the single pixel k. It can not help post-refinement algorithms; 2.
All the pixels in Ω k are considered as inliers. Outliers have strong impacts to the regression, especially when the least square regression is used.
To solve these problems, we refer to RANSAC (random sample consensus) [26], which is a hypothesize-and-verify algorithm that firstly assumes inliers and then calculates the fidelity of the inlier assumption based on all the samples. We firstly make inlier assumption at each pixel k and then evaluate the assumption in Ω k . For each pixel k, we 1. Assume edge consistency in Ω k ;
Evaluate the two assumptions by weighted regression; 4.
Calculate the inlier fidelity of p k based on the residual.
When it is complete, a fidelity map that has the same size as p is available. It is transformed into data weights w and then used in the next round regressions to further suppress the impacts of outliers.

Algorithm
The edge consistency assumption and the inlier assumption imply a small residual e defined as The inlier fidelity w is negatively correlated with e as where (LB, UB) are the lower bound and upper bounds of √ e. When e k is out of the bounds, pixel k is considered as absolute inlier and outlier, respectively. is a small number for numerical stability.
The energy function and the equality constraint of Equation (7) can be combined into By further induction, we have In programming, it is where is a diagonal matrix whose elements all equal , (p) k is the mean value of p in Ω k , and so do the others.
Since e and w are interdependent, an iteration strategy with w 0 = 1 is employed as

Algorithm 1 ALRe
Require: I, p, , LB, UB Ensure: w 1: set t = 0, ∆e t = 1 2: set e t = 1, w t = 1 for all k 3: while ∆e t do 4: calculate w t , w t p, w t I, w t p 2 , w t II T , w t pI by boxfilter 5: for each k do 6: calculate e t+1 k by Equation (11) 10: t = t + 1 11: end while 12: w = w t and the terminal condition is In practice, the iteration number is usually 5∼10. The overall algorithm is summarized in Algorithm 1. The final w is inlier fidelity and 1 − w is outlier likelihood. Note that, those mean values can be calculated by boxfilter with O(N) complexity, where N is the pixel number. Other operations in Equation (8) and Equation (11) are O(N) too. The number of iterations is independent of N. Therefore, the algorithm is O(N) overall. Compared to linear regression without equality constraint [5], which leads to a solution similar to Equation (10), only several mean values are replaced by particular ones. The runtime is even slightly decreased. When handling 640×480 images, each iteration of our ALRe demon (provided in https://github.com/Lilin2015/Author---ALRe (accessed on 5 April 2021)) takes about 0.3 s.

Asymmetry
Linear transformations on I and shifts on p have no impact on the result of w. Firstly, with fixed w, the conclusion of e(p + β p , α I I + β I ) = e(p, I) (14) can be proven based on Equation (10) as Then, the same e results in the same w.
On the other hand, with fixed w, a scaling on p leads to e(α p p, I) = α 2 p e(p, I).
If we simply consider the inverse relationship between √ e and w, it results inw = w/α p , but the real situation is more complex due to the truncated mapping. Anyway, it is clear that ALRe has asymmetric responds to I and p.
The asymmetry fulfills the concept of edge consistency. Contemplate a pair of I and p with modest sharpness 1.
When α p is large, p has sharp edges, e is small only if I and p closely follow the local linear assumption because of the large factor a 2 p in Equation (16). It corresponds to the description "estimate should be smooth if the source is smooth"; 2.
When α p is small, p is smooth, e is small because of the small a 2 p . The sharpness of I is unessential. It corresponds to the description "estimates could be smooth whether the source has an edge or not".
In most applications, I has much more edges than p, but it does not always lead to small w because of this asymmetry.

No False Positive
The main difference between each iteration of ALRe and LRe (linear residual, produced by naive least square regression) is the equality constraint. Previous discussion shows that introducing this constraint does not cost the feature of asymmetry. However, what is the benefit?
To answer this question, we conduct simulations. Firstly, random I and (a, b) are generated in [0, 1]. Then, p is calculated by p k = a T k I k + b k . Based on a preset bad pixel ratio, some pixels of p are modified by random biases in [0.05, 0.5]. Ten levels of bad pixel ratio, from 5% to 50%, are tested. For each level, 10 5 sources and contaminated estimates are generated. Linear residuals of bad pixels with and without equality constraint are recorded.
The results are shown in Figure 1, where LRe means the naive linear residual, and ALRe means the anchored linear residual of the first iteration.  The results of four levels of bad pixel ratio are displayed in Figure 1a-d respectively. As expected, both LRe and ALRe increase when the bias increases. LRe is more sensitive to large biases and ALRe is more sensitive to small biases. However, as the bad pixel ratio increases, mean LRe decreases while mean ALRe keeps stable or even slightly increases. Figure 1e illustrates this phenomenon, where the slope of ALRe is obviously smaller. It means that ALRe is more robust to bad pixel ratio. This is the first benefit.
More importantly, if we further investigate the minimal residual of each test, it comes out that LRe has a false positive problem. The minimal LRe and ALRe are drawn as thin curves in Figure 1a-d. As can be seen, some segments of the blue curves are overlapped with x-axis when the biases are small. The larger the bad pixel ratio, the longer the overlapped segment. For convenience, we term the x-value of the right end of the overlapped segment as false positive threshold, since bad pixels with biases smaller than this value might have zero residuals and be recognized as inliers. Figure 1f illustrates this phenomenon, where the false positive threshold of LRe increases when the bad pixel ratio increases. As a comparison, ALRe has no false positive problem. This is the second and the major benefit.

Applications
We provide four examples of using ALRe, including haze removal, depth estimation, feathering and edge-preserving smoothing. ALRe affects these applications by providing or replacing the data weights in their post-refinements.

Transmission Refinement for Haze Removal
In the field of haze removal, hazy images are considered as haze-free images attenuated by atmospheric lights and transmission maps represents the attenuation ratios. With evenly dispersed haze, attenuation ratios are related to scene depths. Therefore, transmission edges should be consistent with depth edges. Since depth edges are unavailable and mostly happen on color edges, transmission maps are expected to have edge consistency with hazy images.
However, limited by existing technologies, transmission maps usually have unsatisfactory edge consistency; thus a post-refinement based on hazy images is popular. Two examples based on dark channel prior [27] and haze-line model [24] are illustrated in Figure 2. Initial transmission map based on dark channel prior has the problem of block effect, which indicates over-estimated transmissions in the vicinity of large depth jumps [27]. As displayed in Figure 2a, edges of the two images are misaligned near the skyline, where large transmission values of the distant buildings are dilated. Initial transmission map based on haze-line model is estimated using the assumption that the end of each haze-line is haze-free [24]. The assumption is unreliable for short haze-lines, introducing isolated outliers, such as the over-estimated pixels on the sky and roof.
To address the problem of block effect, Zhu et al. [28] detect outliers based on an improved local constant assumption customized for dark channel prior and then employs WLS. As shown in Figure 2c, with correctly revealed outliers, the block effect is well removed without introducing halo-effect. Since the initial transmission map based on haze-line model is unreliable on short haze-lines, Berman et al. [24] detect outliers based on the effective length of haze-line and then employ WLS. As shown in Figure 2d, outliers are correctly revealed, and the transmission map is well refined.
Despite the effectiveness, these outlier detection methods are based on the deep understanding of the assumption, prior and model applied in estimation process. As a comparison, ALRe has similar performance without any of these knowledges. As shown in Figure 2e, according to the law of edge consistency, outliers are also revealed. The refined results based on WLS have trivial differences compared to Zhu et al. [28] and Berman et al. [24].
(a) Source and initial trans. of [28] (b) Source and initial trans. of [24] (c) Weights and refined trans. of [28] (d) Weights and refined trans. of [24] (e) Weights provided by ALRe and corresponding results.  [27] and haze-line model [24] respectively; (c,d) The weight maps and the refined results based on Zhu et al. [28] and Berman et al. [24] respectively; (e) The weight maps based on ALRe and corresponding results.

Refinements in Depth Estimation
Disparity refers to the difference in image locations of a point seen from different views. Disparity maps are inversely proportional to depth maps, whose edges are consistent with color edges. Therefore, they are also expected to have edge consistency with color images. Disparities can be estimated by stereo matching. However, it might be false or invalid on several pixels due to occlusions. An example from Middlebury dataset 2005 [29,30] is shown in Figure 3a (one of a pair). The initial disparity map in Figure 3d is generated by Hosni et al. [25] (without refinement). Outliers can be seen on the left side of most dolls.
Hosni et al. [25] traced outliers by cross check, which requires the image of another view. ALRe is applicable without this extra information. The binary results of these two methods are shown in Figure 3b,c, and the refined maps are displayed in Figure 3e,f. As can be seen, although the seams are missed, ALRe reveals most occluded regions. The refined results are similar and comparable even though ALRe has much less information.
Cross check is not always valid because it requires at least two views of the same object. It is invalid to single view equipment such as RGB-D camera. The depth map of RGB-D camera usually contains unstable edges due to the shifted position and low resolution of depth camera, as illustrated in Figure 4a,b. This problem can be solved by WMF. As shown in Figure 4d, the winding edges are well regularized, but the values of the pointed regions are wrong picked. These regions have zero values because they are invisible to the depth camera and thus should not be considered in picking. With the help of ALRe, these regions are trivial in WMF, and a more convincing result is achieved.

Feathering
Image feathering produces an alpha matte of complex object based on rough binary mask, which can be obtained manually or from other segmentation methods. GF is an efficient tool but not error-tolerant enough since it treats all pixels equally. Masks with obvious errors might lead to halo-effects. As shown in Figure 5d, the result of GF inherits the errors from Figure 5b, leading to the over-estimated and under-estimated results marked by A and B, respectively.  As displayed in Figure 5c, the weights of the mask are very low near the boundaries. It is not surprising since rough masks are never expected to have consistent edges with color images. However, with a closer look, phantom of the edges from both images can be observed, and the regions between them have almost zero fidelities. With this message, a more convincing matte is produced as shown in Figure 5e.

Edge-Preserving Smoothing
Edge-preserving smoothing aims to erase weak edges but preserve strong ones from images. As an edge-preserving filter, GF has the problem of halo-effects. Various methods have been proposed for this problem and various weights have been investigated as described in Equation (3).
ALRe also has the potential to discover strong edges. Firstly, we smooth sharp input by low-pass filter, as shown in Figure 6b. After this indiscriminatingly suppression, weak edges are almost erased but strong edges are still observable. Then, we investigate the edge consistency between the sharp input and the smoothed result. Stronger edges contribute larger residuals, as described in Equation (16) and confirmed in Figure 6c and thus can be recognized and enhanced back. Therefore, with the help of ALRe, edge-preserving can be achieved by enhancing smoothed result guided by sharp input. In this process, GF copies strong edges back in low weight regions. As shown in Figure 6e, the lawn is as smooth as the one in Figure 6d, but the halo-effects near the skyline are avoided.

Summary
Different from noises and biases, outliers are from theoretical or system flaws. They are usually far away from true results and severe against the law of edge consistency. As shown in the examples above, outliers introduce different estimates on the same object, large value jump between similar colors or unexpected edges on a flat region. Most of them can be found without any knowledge but simply the expectation of edge consistency. Compared to prior-based, model-based and hardware-based outlier detection methods, ALRe is unlikely to be the best. However, as a general method, ALRe can be used when specific method is absent, which is a considerable situation. Furthermore, it can be used an extra add-on of existing methods.

Experiments
In this section, we conduct two kinds of quantitative experiments. Firstly, the value of ALRe as an add-on of transmission refinement, disparity refinement and feathering is investigated. Secondly, its outlier detection accuracy is measured and compared with WMF (the kernel of guided filter is adopted) based on synthetic images.
ESR exactly follows the concept of edge consistency but lacks a reasonable minimum. For example, results with constant values always have minimal ESR. Therefore, to make sure what ALRe introduces are improvements rather than over-smoothing, additional metrics measuring output qualities are required. In both parts, the , LB and UB are 0.001, 0.01 and 0.3, respectively. The size of Ω depends.

Transmission Refinement
D-HAZY [31] is a popular dataset which provides abundant hazy and haze-free image pairs. It is built based on Middlebury [32] and NYU Depth [34] respectively. In this comparison, we only use the Middlebury part because of the significantly higher quality. The MSE (mean square error) between haze removal result and groundtruth is used for quality measurement.
In practice, we found out that global biases dominate the results of Berman et al. [24], while outliers are trivial. As a comparison, the outliers of block effect in the rough outputs of Zhu et al. [28] challenge both post-refinement and ALRe. Therefore, the experiment is based on Zhu et al. [28]. We exactly follow the configurations of Zhu et al. [28], and the Ω for ALRe has the same size (51×51). For each sample, we produce the rough transmission map with block effect, the refined map based on WLS without ALRe and the refined map with ALRe. Transmission maps are evaluated by ESR, and haze removal results are evaluated by MSE.
The results are displayed in Figure 7, where the result of Zhu et al. [28] is marked as WLS+WCA (weighted constant assumption). As can be observed, naive WLS improves edge consistency but barely improves haze removal quality. With the help of ALRe, both improvements are significant and even comparable to Zhu et al. [28].

Disparity Refinement
Middlebury [32] is a widely used dataset with stereo images and groundtruth disparities. The ER (error ratio) of estimated disparity map is used for quality measurement. It is the percentage of bad pixels with absolute error no less than 1 (pixels with unknown disparity are excluded from statistics). As pointed out by Ma et al. [11], textureless region dominate the statistics while outliers are trivial. Therefore, we only use the 2001 dataset, where the ERs of initial results are all less than 5.
The size of WMF is 11×11 based on the configuration of Ma et al. [11]. A larger WMF could erase more outliers but also smear image contents. However, finding outliers before modifications based on a large ALRe is safe. Therefore, we set the size of ALRe to 21×21. For each sample, we produce the rough disparity map based on cost-volume method [11] (boxfilter for cost aggregation), the refined map based on WMF without ALRe and the refined map with ALRe. Disparity maps are evaluated by ESR and ER.
The results of each sample are displayed in Figure 8. The y-axis is ln(ESR). As can be inspected, WMF introduces significant boosts on both edge consistency and accuracy, and ALRe is able to introduce further improvements. An example of this small but stable improvement is displayed in Figure 9. As can be observed in Figure 9c,d, WMF with ALRe produces less spikes.  Figure 8. Effect of ALRe on WMF in disparity post-refinement. The errors of cost-volume method [25] are marked by the dots with sample names. Each first linked dot is the error of WMF, and the next dot is the error of WMF with ALRe.

Feathering
Alpha Matting [33] is a dataset providing abundant images and groundtruth alpha mattes. The MSE between estimated matte and groundtruth is used for quality measurement. As shown in Figure 11d, the rough mask of Alpha matting dataset [33] is triple, including foreground region, background region and unknown pixels. To produce rough binary masks, we fill each unknown pixel by the label of its closest region. To prevent over-large errors, samples containing unknown pixels far from both regions (the Euclidian distance is more than 25) are excluded. Finally, the five samples in Figure 10 are selected.
The size of GF is 35 × 35. A larger GF could cover more reliable labels but worsen the halo-effect and texture-copy problems. However, finding outliers based on a large ALRe is safe. Therefore, we use a 51 × 51 ALRe, which can stride over the largest unknown region. For each sample, we produce the rough binary mask, the refined matte based on GF without ALRe and the refined matte with ALRe.
The results of each sample are displayed in Figure 10, where GF introduces improvements on both aspects and ALRe helps GF to introduce more. An example is illustrated in Figure 11. The result of GF shown in Figure 11b has obvious halo-effect and texture-copy problems due to its large size. However, the large size is necessary because the large unknown region. If we dilate the foreground region, the problems become less obvious but still exist, as shown in Figure 11c. As shown in Figure 11e and Figure 11f, with the help of ALRe, the problems are solved, and the refined mattes are barely affected by the dilation.

Outlier Detection
The IoU (intersection over union) of outlier detection result and groundtruth is used for evaluation.
MASK and GT are binary images, whose pixel x equals 1 if p(x) is asserted as an outlier. The MASK of ALRe is MASK ALRe (p, I) k = 1, ALRe(p, I) k < 0.05 0, ALRe(p, I) k 0.05 .
The MASK of WMF is produced based on the intuition that pixels greatly changed after filtering are outliers; thus, Source images I are provided by Middlebury 2014 [35]. The groundtruth estimate q is produced based on parameter map (a, b) as q k = a T k I + b k . The map (a, b) is generated by smoothing a fully random matrix by R × R boxfilter. Contaminated estimate p is synthesized by adding outliers to q. Two kinds of outliers are tested, including spikes and regions. The number of outliers is controlled by M.
The task is more challenging with smaller R and larger M. We tested 22 kinds of R and 3 kinds of M. The size of Ω for ALRe and WMF is 25×25 (the inputs are 640×480). Larger R leads to larger mean(ALRe(q, I)), which indicates the fidelity of the local linear assumption. It is the cornerstone of ALRe, and therefore, we term it as ALRe expectation.
The results are illustrated in Figure 12. As can be seen, both ALRe and WMF achieve high accuracy at spike detection. ALRe fails when the ALRe expectation is lower than 0.2. The fewer the outliers, the worse the IoU. It means that ALRe has a true negative problem when the local linear assumption is not established. However, ALRe performs significantly better than WMF at bad region detection. The mean IoUs of ALRe corresponding to the increasing M are 0.978, 0.958, 0.868, while the ones of WMF are 0.814, 0.727, 0.556. The gap is approximately 0.2. ALRe is robust in this task even though the ALRe expectation is very low. For example, detecting outliers from Figure 13b (the ALRe expectation is less than 0.2) is very challenging. WMF only achieves an IoU equals 0.6508 because many outliers happen to be the medians. However, ALRe remains a high IoU equals 0.9027. The undesired hollows in MASK WMF are mostly avoided in MASK ALRe . Furthermore, the effects of source contrast and outlier strength are tested by shrinking the intensities of p and I toward their mean values. As shown in Figure 12, ALRe maintains high IoUs until the contrast is lower than 70% or the outlier strength is lower than 60%.

Conclusions
In this paper, we address the problem of general outlier detection. Edge consistency is exploited, based on which, a hypothesize-and-verify algorithm termed ALRe is proposed. Analysis and comparison with other options shows that ALRe has good features including asymmetry, no false positive problem and linear complexity. Examples on four applications show that ALRe could provide meaningful detection result and even replace specifically designed method without obvious quality degradation. Experiments on three datasets demonstrate that ALRe could help post-refinement algorithms to further improve contaminated estimates. Experiments on synthetic images show that ALRe is as effective as the mainstream WMF at spike detection and is significantly better at bad region detection. The improvements measured by IoU are about 0.2.
In conclusion, ALRe is a feasible solution of the general outlier detection problem. It can be used when the estimation process is unknown, when a specific method is absent, or simply as an extra add-on of post-refinement algorithms.