In this work, we present an approach to the detection of outliers in certain polygonal chains. These originate from images of mountains which are first segmented in order to extract the mountains silhouette. In general, the aim of our framework is to recognise the mountain in the image in order to overcome the problem of large amounts of images on the internet that are not tagged and thus cannot be searched in a sensible fashion. The appearance of outliers in our case is specific by them either being obstacles in the image that are in front of the mountain or they are due to problems during the silhouette extraction step. In this work, we show, how outliers are defined in our context, namely as sub-sequences that are found by a double threshold technique. Therefore, we describe how the anomaly scores for single vertices in the polygonal chains are computed via a histogram distance based approach. We also introduce an improved way to compute reference data and outlier scores and show that this changes allow for significant better outlier detection results.
Social networks and image sharing platforms enable users to easily share their
photos, with millions of pictures uploaded every day. However, most of these
photos are not properly tagged. Because of this, they are not easily accessible
since they cannot be simply searched for. The aim of our framework presented
in [
Since our idea is to be able to annotate every image of a mountain, even
without GPS information, we have to extract much more precise silhouettes
than approaches that will work on GPS tagged images, only. Therefore, it is of
imminent importance to correct errors that occur during the initial segmentation
step. In this work, we present an enhancement to our outlier detection step from
[
There are approaches for automatic tagging, which provide solutions for other
motifs than mountains [
The area of mountain recognition is rather small. Baatz et al. [
A silhouette is essentially a two dimensional polygonal chain. However, there
is not much work on outlier detection on polygonal chains. A closely related
problem is outlier detection in time series. There are many approaches to this,
such as Hot Sax [
Another, but less closely related, approach to outlier detection in time series
is change point detection [
In this section we shortly introduce our adaptive mountain silhouette (AdaMS)
framework that initially has been presented in [
AdaMS is our approach to solve the first of these problems. It uses a grid based segmentation algorithm for the initial silhouette extraction. This silhouette is then, as a second step, searched for outliers which then get classified. Regions around correctable outliers are then resegmented with a di↵ erent parameter set. The resulting silhouette is again searched for outliers, until no more correctable outliers are found or a maximum number of iterations has been reached.
The identification of the silhouette itself can be divided into two problems, namely the mapping to a known silhouette and the creation of the reference data, i.e. the known silhouettes. Due to the great number of mountains, the mapping of an extracted silhouette to a labelled silhouette has to be precise and with as little computing cost as possible. Therefore it seems advisable to use a step wise process that uses fast to compute distance measures in a first step in order to exclude reference data with low resemblance. As the number of relevant silhouettes decreases, more precise similarity measures can be applied.
The creation of the reference data is a task, that could theoretically be carried out by humans. However, that would be an immense workload because one labelled silhouette per mountain would not su ce to support a reliable identification. This is because mountains look di↵ erent from di↵ erent angles. It seems much more feasible to automatically extract the reference silhouettes from digital elevation maps. 4
For finding outliers, we first have to define outliers for our application case. Based on this definition, we show the basic AdaMS outlier detection and then introduce recent improvements. 4.1
Outlier Definition
A silhouette is a two dimensional polygonal chain that can be converted to a
relative silhouette:
Definition 1 A relative silhouette RS = (v1, . . . , vn), n > 0, is a polygonal
chain with vi = (li, ai) for all 1 i n, where li > 0 is the length of a line
segment and ai 2 ( 180 , 180 ] is the angle relative to the x-axis. [
On such a relative silhouette we want to find unusual parts that are caused by obstacles such as trees or segmentation faults due to low contrast. So an outlier o = (vi, . . . , vj ), 1 i < j n, is a part of a relative silhouette, where the combination of vertices vi, . . . , vj does not fit the usual patterns in relative silhouettes extracted from mountain images. This is introduced formally in the following definition.
Definition 2 Let l > 0, and RS = (v1, . . . , vn) be a relative silhouette.
We call o = (vi, . . . , vj ) an l-outlier if the following is true:
1. For all vk, i k j, it holds that vk is a weak anomaly.
2. There exist m1, m2 2 {i, . . . , j} such that m2 m1
m1 k m2, it holds that vk is a strong anomaly. [
Definition 2 mentions strong and weak anomalies. These, in contrast to outliers, are single vertices that have unusual properties, that is, high anomaly scores. We therefore show how these concepts can be defined. Anomaly scores are computed via histograms of parts of relative silhouettes.
Definition 3 Given a relative silhouette RS, then HRS (s, l) denotes the
histogram consisting of the points vs, . . . , vs+l 1 of RS and HRS denotes the
histogram over all vertices of RS. [
Based on these histograms and the distance to the reference histogram Href , we are now able to introduce the vertices’ anomaly scores: Definition 4 Given a relative silhouette RS = (v1, . . . , vn) and a reference histogram Href .
The anomaly score an(vi) := 1 l
i
X j=i l+1 dj of vertex vi is the average of the distances dj = dist(HRS (j, l), HR).
With the anomaly scores we can now finally introduce the di↵ erent kinds of anomalies used in definition 2: Definition 5 Let RS = (v1, . . . , vn) be the silhouette of an image with corresponding anomaly scores an(vi) for vertex vi, reference anomaly score distribution mean µ and standard deviation and two thresholds 0 < ⌧ out < ⌧ in.
Then we call vi a weak anomaly if and a strong anomaly if an(vi)
µ + ⌧ out · an(vi)
µ + ⌧ in · . [
This shows, that an outlier in our case is an application of a double threshold technique. The idea here is that often, within an obstacle or a segmentation fault, only small parts of the outlier consist of vertices with unusually high anomaly scores. The rest of the outlier consists of vertices whose anomaly scores are still high, but on their own would not su ce to identify an outlier. Figure 1 shows such an example.
SingleRef Outlier Detection and Reference Data Computation
As in [
Given the anomaly values an(vi) for the vertices, finding the maximum loutliers according to definition 2 is straightforward. In the first step, we search for sequences of vertices with a length of at least l that all are strong anomalies. Once we have found such a sequence, we let it grow by adding vertices that are neighbours of the currently detected outlier and weak anomalies on both sides.
In regard to reference data computation, the algorithm gets a selection of outlier free silhouettes that where chosen by hand and computes a single reference histogram Href of all those silhouettes. We therefore refer to this version of the algorithm as SingleRef outlier detection. The statistical properties µ and are then computed by using the same window lengths as in the actual outlier detection to compute the anomaly score of every vertex in the reference silhouettes. 4.3
MultiRef – Improving SingleRef Computing one histogram, in a certain manner, aggregates the data represented by the histogram. Due to the di↵ erences in details, a stronger aggregation results in higher standard deviation of the single data points to this aggregates than a weaker aggregation. This, in turn, leads to obscured real anomalies, since distances to the reference data are in general rather high. As the evaluation chapter shows, this leads to either high rates of false positives or relatively low detection rates for SingleRef.
A solution to this problem would be the usage of multiple reference histograms. Intuitively, one would choose one histogram per silhouette, resulting in Histograms Hr1ef , . . . , Hrnef if we assume n reference silhouettes. In order to use more than one reference histogram, however, we have to adjust the distance computation. The base distance used in AdaMS is the following: Definition 6 Let G = (g1, . . . , gn), H = (h1, . . . , hn) be histograms with n buckets.
The above average distance of G to H is defined by dist(G, H) := max(|aab(G)|, |aab(H)|) |aab(G) \ aab(H)|, where aab(F ) := ( i 2 {1, . . . , n} fi
n 1 X fi n i=1 ) with F = (f1, . . . , fn) being a histogram with n buckets.
Essentially, by the above average distance, the number of above average buckets that are the same in both histograms is subtracted from the higher number of above average filled buckets.
Theorem 7 The above average distance from definition 6 is a pseudometric.
For the proof of this theorem see appendix A.
Now, when comparing a histogram with not just one reference histogram but several, we compute the above average distance to all reference histograms and then choose the minimum of that distances.
Definition 8 Given a histogram H and reference histograms Hr1ef , . . . , Hrnef , then distmr(H) := min 1 i n dist(H, Hrief ) is called the min-ref distance.
As the number of reference silhouettes is potentially large and it is beneficial
to add further silhouettes free of outliers to the reference data, it is clear that
the usage of a reference histogram per reference silhouette is not feasible and
the number of histograms has to be reduced. On the other hand, we want to
minimise the loss of detail due to aggregation. We therefore utilise a k-means
clustering [
By this, we are able to reduce the number of reference silhouettes to any given k while ensuring, that we loose as little detail as possible, because the subadditivity holds for the above average distance. This means, the distance to the cluster representative is an upper bound on the distance to the closest silhouette’s histogram. We ensure small distances between representatives and members of the cluster by clustering with random start representatives 1000 times and choosing the clustering with the smallest quadratic distance. It is also noteworthy, that by setting k = 1 we only get one reference silhouette that is identical to the reference silhouette of the SingleRef method.
By this, as the evaluation shows, we are able to achieve better outlier detection without changing our outlier detection algorithm as such nor do we need more reference data. 4.4
Further Steps
The next steps after identifying the outliers are to classify them into obstacles in
the picture and errors in the segmentation step, for example due to low contrast
between parts of the mountain and the sky. As described in [
In order to evaluate the approaches introduced in the previous section, we
manually annotated a test set of 111 outliers from 14 silhouettes, that, in total, consist
of 3580 vertices. The silhouettes have been automatically extracted from the
images by a variant of the the segmentation algorithm presented in [
The outlier detection algorithm has been trained with 48 silhouettes that are mostly free of outliers and have been extracted with the same mechanism as described above. These have been clustered 1000 times per number of clusters and the clustering with the lowest overall quadratic distance of histograms in respect to their cluster representative has been chosen.
We first evaluated the precision and recall based on detected outlier vertices for di↵ erent values for k, the number of reference silhouette clusters and thus reference histograms. As parameter set we chose the minimum length for an inner outlier l = 3. The inner and outer thresholds have been set to ⌧ in = 2 and ⌧ out = 1. The results of this are shown in table 1. Note here, that for k = 48 no clustering is used, but here one reference histogram per reference silhouette is used.
Precision and recall are computed by counting the vertices that have been declared as parts of outliers correctly and dividing that number by the total number of detected outlier vertices respectively the total number of annotated outlier vertices. The last number is shown in the last row of the table. It can be seen here, that MultiRef, for every tested value of k shows better results than SingleRef. Especially recall is much better than with SingleRef and gets higher Method
Value overall with increasing k. Interestingly, while there is a huge improvement in recall from k = 20 to k = 30, recall does not get any better when using one histogram per reference silhouette. Precision, too, is higher for the MultiRef variants in respect to SingleRef, but it is noteworthy here, that, instead of rising with the number of clusters, a maximum is reached for k = 7 respectively k = 10 and for bigger values, a slight decrease can be noticed. Note here, that the results in table 1 are given without carrying out the classifying of outliers. By that step, some outliers will be classified as false positives and thus precision after classification should increase.
Table 1 also shows, that for silhouettes 2 and 5, no correct outliers have been found at all. The outliers in both silhouettes are rather short. The three outliers in silhouette 2 have a length of 8, 9 and 13 vertices and the four outliers in silhouette 5 have a length of 9, 10, 12 and 15 vertices.
Based on this observation, table 2 shows the number of outliers that have been hit by the detection algorithm. The same parameter set as above has been used for this. An outlier is counted as being hit by the detection algorithm, if at least one vertex of it has been detected as being part of an outlier. In context with AdaMS, if this happens, the silhouette will be recomputed in this region and can thus be corrected. It is clear, that all algorithms have problems with smaller outliers. For the extraction of good silhouettes, it is more important to find huge outliers, and our detection rates for those are promising, in general. The detection rate increases with the length of the outlier for every variant. On Method |out| 5 5 < |out| 10 10 < |out| 20 20 < |out| 50 50 < |out| Total SingleRef 0 1 2 5 10 18 k = 3 2 5 7 14 12 40 k = 5 5 7 9 15 13 49 k = 7 4 5 7 14 13 43 k = 10 4 5 8 14 13 44 k = 20 4 8 8 15 12 47 k = 30 6 10 11 16 15 58 k = 48 6 10 11 16 15 58 #Outliers 18 38 19 21 15 111 Table 2. Number of detected outliers. The length of outliers is denoted by |out|. Thresholds are ⌧ in = 2 and ⌧ out = 1, l = 3. the other hand, with increasing k, the detection rate in general increases, too. Interestingly, for k = 5 more outliers have been detected than for surrounding values of k. However, due to the relatively small numbers of outliers used in our evaluation, this might be coincidence.
⌧ in ⌧ out l |out| 20 20 < |out| 50 50 < |out| Total Precision Recall 2 1 3 21 15 13 49 74 54
The results in table 3 show the results of our investigation of the e↵ ects of parameter changes. Essentially, lowering ⌧ in or l results in a greater number of detected outliers, while raising that values reduces the number of outliers. Changes to ⌧ out a↵ ect the size of detected outliers. The lower ⌧ out becomes, the bigger are the resulting outliers. Due to overlaps with the real outliers, lowering of one of the values leads to higher recall and decreased precision. Increasing them raises precision but induces losses to recall.
In summary, the results show that even for the worst choice of k, the number of hit outliers is more than two times higher than that detected by SingleRef, while at the same time precision and recall are increased.
In this work, we have presented our definition of outliers and our approach to make the detection of outliers in polygonal chains that represent silhouettes extracted from pictures of mountains more e↵ ective. Our results show, that the MultiRef variant introduced in this work greatly improves the outlier detection results. The number of detected outliers is increased by a factor of two to three, depending on the number of clusters, while precision and recall are also increased.
However, there are some points that we want to address in the future. One
of the main questions is, whether our distance function as given in definition 6 is
ideal or if a more elaborate histogram distance function such as the earthmover’s
distance [
A
The fact of the above average distance being a pseudometric is of importance since it ensures that the triangle equation is satisfied by that construct. From this it can be derived that the greater the distance between two histograms is, the greater the di↵ erence between those is and there are no short cuts by using intermediate histograms.
Proof. In order to show that the above average distance is a pseudometric, four properties have to be shown. Let g, h, k be histograms with the same number of buckets.
Non-negativity dist(g, h) 0. This is trivial since |aab(g)| and |aab(h)| |aab(g) \ aab(h)|, thus |aab(g) \ aab(h)| max(|aab(g)|, |aab(h)|) |aab(g) \ aab(h)|.
Identity of indiscernibles dist(g, g) = max(|aab(g)|, |aab(g)|)
|aab(g) \ aab(g)| = |aab(g)|
|aab(g)| = 0.
Symmetry dist(g, h) = max(|aab(g)|, |aab(h)|) = max(|aab(h)|, |aab(g)|) = dist(h, g) |aab(g) \ aab(h)| |aab(h) \ aab(g)| since both max(·, ·) and the intersection of sets are symmetric functions.
Case 1 Now, let |aab(h)| |aab(k)|. Then it holds that dist(k, h) = |b| + |d| and dist(g, k) = |a| + |d|, since |aab(g)| |aab(h)| |aab(k)|. Thus, in this case because dist(g, k) + dist(k, h)
dist(g, h) =|a| + |d| + |b| + |d| =|b| + 2|d| |f | 0, |a|
|f | |aab(h)|
|aab(k)| ) |b| + |d| + |e| + |m|
|c| + |e| + |f | + |m| ) |b| + |d| |c| + |f | |f |.
Case 2 Assume now, that |aab(h)| < |aab(k)|, so dist(k, h) = |c| + |f |. Case 2.1 Let |aab(g)| |aab(k)|. It follows that dist(g, k) + dist(k, h)
dist(g, h) =|d| + |c| =|a| + |d| + |c| + |f | 0.
|a|
|f | dist(g, k) + dist(k, h)
dist(g, h) =|c| + |e| + |c| + |f | =2|c| + |e| |a| 0.
|a| |f | Case 2.2 The last case to be considered occurs if |aab(g)| < |aab(k)| which results in dist(g, k) = |c| + |e|. Then This is because of a similar argument to case 1, because |aab(g)| ) |c| + |e| |a| + |d| |a|.