With the rise of digital photography and easy sharing of images over the internet, a huge amount of images with no notion of what they are showing exists. In order to overcome this problem, we - for the example of mountain recognition introduce a method, that is able to automatically recognise a mountain shown in a photography. Our method does not require GPS information stored in the image, since most images are not GPS tagged, either because of the absence of a GPS sensor in the device or because it has been deactivated for a lesser power consumption, which often is the case with smartphones. Instead, we propose a method that is able to automatically extract the mountain's silhouette from a given image. This silhouette is then cleaned by removing artefacts and outliers, such as trees and clouds, with a histogram based approach. Finally, the cleaned silhouette can be compared to reference data in order to recognise the mountain that is shown in the picture. For this, time series comparison techniques can be used to find matching silhouettes. However, because of the huge number of reference silhouettes to compare against, we argue, that a preselection of those silhouettes is necessary and point out approaches to this problem.
I.4.8 [IMAGE PROCESSING AND COMPUTER VISION]: Scene Analysis—Object recognition; I.4.6 [IMAGE PROCESSING AND COMPUTER VISION]: Segmentation—Edge and feature detection; H.2.8 [DATABASE MANAGEMENT]: Database Applications —Data mining
Sharing our experiences with digital images is a significant
part of our today’s life, which is partly a result of the high
availability of digital cameras, like in smartphones, and the
high use of social networks, that simplifies the publication
and sharing of images. As a consequence, the number of
images in the world wide web increases significantly. For
example, this can be seen on the image sharing platform
Instagram, where users share an average of 70 million new
photos per day [
As a result of such high numbers of images, searching photos which show specific objects is challenging, because the majority of these images is not properly tagged with the names of every object seen in them. So the need for efficient algorithms for automatic object recognition rises. In the last decades there were many advances in this research field, but especially the automatic identification of landmarks, which are subject to weather changes, areal erosion and vegetation, is still a challenging task, even if the amount of images with attached GPS data, which marks the geo-position of the camera when the photo was shot, is rising.
The growing spread of devices with the capability of generating GPS tags for the images, like smartphones and digital cameras with GPS units, enables many possibilities for an subsequent geo-localisation of images, due to the fact that GPS tags can significantly reduce the number of possible sights, buildings or landmarks to compare with. However, there exist too many images without the advantage of GPS tags, so that an automatic geo-localisation without prior knowledge of the camera position is still a valuable aim.
Our focus lies on the automatic landmark recognition, which we will describe by using the example of mountain recognition in images. To solve the question, which mountain can be seen on an given image, we match the skyline of the mountain in the image with silhouettes of mountains in our database. For this purpose, we have to automatically extract the exact skyline from the image, which is a difficult task, because the segmentation of the image can lead to artefacts, for instance due to weather conditions, noise, obstacles or overexposure.
In this paper we introduce a baseline segmentation algorithm, which uses an outlier detection algorithm to identify and eliminate these artefacts. The article is structured as follows: In the next section we discuss other papers related to our algorithm. We then introduce our algorithm, which consists of the three steps silhouette extraction, silhouette cleaning and silhouette matching. The section of the latter one will be a perspective of how to use the cleaned silhouette in further steps. The last chapter summarises this paper and outlines future work.
The amount of publications for automated mountain
recognition increased significantly in the last two decades.
Given a high number of publicly available digital elevation
maps (DEM), the consensus in many publications [
Many approaches, like [
Baboud et al. [
All three approaches show good results for their issue,
but the need for GPS data for the processed image does
not match our problem specifications, different from Baatz
et al. [
Tao et al. [
The silhouette recognition process is basically a process in three steps. The first step is the extraction of the silhouette from a given picture. This silhouette is stored as a polygonal chain. During the second step, this silhouette is cleaned by identifying and removing outliers. The cleaned silhouette is then used as the input to the third and final step, which consists of matching the silhouette against the reference data in order to be able to identify the structure in the picture. 3.1
Extracting the silhouette is the first step in the mountain
identification process described in this paper. The task of
this step is the separation of the sky from the rest of the
processed image. We therefore have a binary segmentation
task to solve, in which we check every pixel p of an image and
decide if p shows a part of the sky or not. For a human this
would be easy to do in most cases, even though it would
be too much work and time to segment great numbers of
pictures manually. Because of that, we use a growing seed
algorithm, like the algorithm described in [
The segmentation of an image generally suffers from different problems, like under-/overexposure, which results in a smaller difference between the pixel colours, or blur, which can be, for example, a result of a lossy compression of the image. In addition, our binary segmentation task has even some own problems to deal with. The first difficulty is a consequence of the motif itself, because the weather in mountainous terrain is very volatile. This and the fact that, for example in the alps, many mountain peaks are covered with snow, can make the extraction of the mountain silhouette out of an image imprecise. Furthermore differently coloured bands of cloud can lead to an extracted silhouette which lies in the sky and is therefore not part of the real skyline. The second one is a result of possible obstacles, which hide the real silhouette of the mountain or lead to smaller segments within the sky segment.
Even though we are aware of these problems, our naive segmentation algorithm cannot handle all of them. For the identification of artefacts as result of segmentation errors, we use the second step of our chain, which is described in section 3.2. Our segmentation algorithm uses the upper row of pixels as seed for the sky segment. This means that we mark the upper pixels as sky and process every neighbouring pixel to let this segment grow. For this purpose we first convert the processed photo to a gray-scale image G. Now we can define VG as overall variance of the brightness values. Having VG, we now process every pixel p(x,y) which is not a part of the sky segment and mark it as sky candidate, if for p(x,y) it holds that √
Bp(x,y) − meanrp(x,y) < γ · VG with Bp(x,y) the brightness of the pixel p(x,y), meanrp(x,y) as the mean of the brightness in an neighbourhood of the pixel with the radius of r and γ as a factor to scale the impact of the standard derivation. This means that we mark a pixel, if its distance to a local mean of brightness values is smaller than a fixed percentage of the global standard derivation of all brightness values. The idea behind this term is, that the border between sky and ground has in most cases a stronger contrast than the rest of the image, especially the sky. Therefore, the distance to the mean will be higher at the skyline as it will be at the border of possible clouds. With the connection of the upper bound to the standard derivation, we want to take into account the images where the brightness is very homogenous, for example due to overexposure, and therefore the contrast of the skyline decreases.
In our experience this naive assumption shows good
results for r = 5 and γ = 0.1 on most images out of the swiss
dataset published in [
For the silhouette extraction, we search a silhouette S = (v1, . . . , vn) where every vertex vi = (xi, yi) is a two dimensional point where xi describes the x-coordinate and yi describes the y-coordinate of that point in the picture. We start at the upper left pixel p(0,0) and search for the first nonsky pixel as start vertex v1 for our polygonal chain, which lies on the left pixel column with x1 = 0. Now, we have two possibilities: First, we can find no pixel, which results in checking the next column until we find a pixel or we have reached the lower right pixel of the image. Otherwise, if a possible skyline pixel was found, the algorithm tracks the transition between the sky and the ground in the following manner.
Having vi as the last extracted vertex of the silhouette, the algorithm checks the 8-connected neighbours of this point (see the right side of figure 1) and chooses the non-sky point as next vertex which has the lowest angle between the incoming line, defined by the two last vertices vi−1 and vi, and the outgoing line, defined by vi and the neighbouring point. This can easily be done, as shown in figure 3, by checking the 8-connected neighbours from vi in clockwise direction, starting at the predecessor. The only exception is the start point v1, where we set v0 = (−1, y1). This means that we choose in this case the left direct neighbour, which lies outside of the image, as predecessor.
2 1 vi−1 0 3 vi 7 4 5 6
Now, we have the border of the mountain as chain of neighbouring pixels. To reduce the amount of vertices without loosing any information, we eliminate all vertices which bring no further information gain to the final silhouette in the last step of the extraction phase. For this, we define the information gain I of a vertex vj , with 1 < j < n, as Ivj = (1, if ∠vj−1vj vj+1 6= 180◦ 0
otherwise.
This means that every vertex which lies on one line with his predecessor and successor carries no further information for the extracted silhouette. After deleting every vertex with Ivj = 0, we obtain our final polygonal chain, which can now be analyzed in the the cleaning phase described in the following section. 3.2
The extracted silhouette from the previous step may contain different disturbances. In this step, we try to get rid of those, so that they cannot affect the step of silhouette matching that gets described in section 3.3. Examples for such disturbances are manifold, ranging from objects in front of the mountain, such as trees, to errors produced during the extraction process that can be caused by a low contrast between the mountain line and the sky. Essentially, after finding an outlier, we currently cut elevations within this part of the silhouette away.
Some of such outliers are showcased in figure 4. Here, the black line is the silhouette that has been extracted by the extraction step as described in section 3.1. The red parts are those parts of the silhouette, that are automatically detected as outliers. Examples for outliers are the tree tops to the left, that have correctly been marked as outliers. In the center of the picture, there is a part of the mountain, that has been cut out. Here the contrast between rock and blue sky gets to low for the extraction step to distinguish them. Right next to this, clouds around the lower peak in the back l2
v1| = v|2 − a1 = 45◦ v2 get recognised as mountain. Since the outline of this outlier is not atypical for a mountain silhouette, this outlier is not recognised. Farther to the right, there are two other outliers where clouds are recognised as mountain by the extraction step. These are, in this case, marked red and such detected by the silhouette cleaning step.
Note, that there are a few parts of the silhouette that get marked as outliers but are not described above. These are false positives. However, since the image here is used to showcase the different kind of outliers, these are not discussed here.
The silhouette cleaning part of our algorithm is, again, divided into three parts. As an input, it gets the silhouette S = (v1, . . . , vn) extracted from a picture.
For the recognition of patterns inside the polygonal chain, this representation has disadvantages, because all vertices are given in absolute positions. For outlier detection, a model where similar structures do look similar in their representation is beneficial. Therefore, we convert S to a representation AP = (ap1, . . . , apn), with api = (li, ai). Here, we set li = (|vi − vi−1|, if i > 1
0 else and ai as the angle between the vector vi+1 − vi, and the x-axis for i < n and an = 0◦. Figure 5 illustrates this. During this step, points where the angle does not change are removed. Also, artefacts consisting of angles of 180◦ between two following segments get removed.
The basic idea of the outlier detection method itself is
to compare histograms created from parts of the polygonal
chain AP to a reference histogram. The latter hereby is
created from the silhouettes of the ground truth data as
given in [
The mentioned histograms consist of the two dimensions segment length and angle size, just as the points in the transformed polygonal chain AP , and are normalised. This means, that the sum of the frequencies of each bucket is 1. For the reference data, we compute one histogram from each image’s silhouette. Finally, the mean of all these histograms is computed and becomes the reference histogram Hr.
In order to find outliers, we use a sliding window approach over the polygonal chain APi of a given input image. We therefore use a section of m successive segments api, . . . , api+m−1 in order to compute a histogram Hi with the same bucket distribution as in Hr. Then, for every point used to compute Hi, we store the distance between Hi and Hr. By this approach, for most points, multiple distance values get stored when the sliding window is moved on. The final distance di for a point api is now computed as the average distance of all distances stored for this point.
As distance function in this case we use the one given in the following
Definition 1. Let G = (g1, . . . , gk), H = (h1, . . . , hk) be normalised histograms with the same bucket distribution.
The above average distance of G to H is defined by D(G, H) := max(|aab(G)|, |aab(H)|) − |aab(G) ∩ aab(H)|, where 1 aab(F ) := i ∈ {1, . . . , k} fi ≥ k with F being a normalised histogram with k buckets. This can be implemented to compute in linear time to the number of buckets, or, for histograms of a fixed length, in constant time.
Based on a number of images used as training data, in the same way as described above, the medium distance μ and the standard deviation σ can be determined. We use these precomputed values in order to find two thresholds τin > τout, such that we can characterise a point api as a strong anomaly if it holds that its distance and a weak anomaly if di ≥ μ + τin · σ di ≥ μ + τout · σ.
We also determine a length threshold l. For a part of the polygonal chain, to be recognised as an outlier, it must hold that at least l successive points api, . . . , api+l−1 must be strong anomalies. An outlier can have any length that is equal to or bigger than l. Finally, if we find such an outlier, we expand it by adding points to it that are adjacent to the outlier and weak anomalies. By this, it is possible for outliers to merge.
As an example, say, ap7, . . . , ap20 are strong anomalies because their distances d7, . . . , d20 are bigger than μ+τin ·σ. If we set l = 4 for this example, these thirteen points are recognised as an outlier o = {7, . . . , 20}. Now, let us assume that ap5 and ap6 are weak anomalies as well as ap22. Then ap6 and ap5 belong to the extended outlier, because they are both adjacent to the outlier. On the other hand, ap22 does not belong to the extended outlier, because ap21 is not part of the outlier since it is not a weak anomaly.
Once all outliers have been detected, the next step is to remove them. Currently, we use a very simple approach for this where, in the original silhouette S, the overhanging part of the outlier is replaced by a straight line. This is based on the notion, that the reasons for most outliers in the silhouette are either trees or clouds. By just removing them, in many cases, we get results that resemble the original shape of the mountain in an easy way.
Let o = {i, . . . , j} with i + l ≤ j be an outlier. Then we draw a straight line from vi to vj. Now, while the distance between vs, starting with s = i + 1, and that straight is smaller than a preset value d, we find the vertex vs with the largest index, that is close enough to the original straight line. The same is done from the other end of the outlier so that we find a vertex ve. This results in four vertices’ indices j ≤ s < e ≤ j1. From this, the part between vs and ve is now finally replaced by a straight line between these two vertices.
By this, we obtain a cleaned silhouette that can be used in further steps for the silhouette matching. 3.3
Once the silhouette is extracted and cleared of outliers, it is now time to match it to the reference data in order to determine the mountain that is shown by the picture. Currently, we have not implemented any method, yet. However, we will introduce some methods that we are going to test in the future.
The converted silhouettes AP = (ap1, . . . , apn) from the
previous section can be easily changed to be interpreted as
time series by setting AP 0 = (ap01, . . . , ap0n) where
i
ap0i = (li0, vi) = (X li, vi)
j=1
for api = (li, vi). By this conversion, every point ap0i has
the length of the polygonal chain until that point as its first
component. Since li > 0 for all i > 1, the length component
of AP 0 is strictly monotonic increasing, just as the time
dimension in a time series. This is because we do not allow
identical points in our silhouette. With this, it is possible
to compare different silhouettes for similarity by using time
series comparison techniques such as [
Due to the great number of mountains and peaks that exist and on the notion, that every peak can be photographed from different angles, there are hundreds of thousands of silhouettes to match for each query image. Due to this it is clear, that even with a high-performance matching method a preselection is necessary.
There exist many methods suitable for this, such as the
technique presented in [
Therefore, we aim to reuse the idea of our outlier detection method for matching. Instead of computing histograms of short sequences of the silhouette, in this case the histogram HS over the whole silhouette AP is computed. This is then compared to the reference images’ histograms HRi , i ∈ {1, . . . , nref } with nref the number of the reference image, which we, as discussed in section 3.2, have to compute anyway. The comparison between two histograms, with our distance function, is linear to the number of buckets in the histograms, or, since this number is fixed, constant. Now, let d(HS, HRi ) denote the distance between the histogram of the new silhouette S and the ith reference histogram. If d(HS, HRi ) is small, this does not necessarily mean, that the silhouettes are identical or even really similar, because the histogram representation does not preserve the order of the contained elements. On the other hand, if the distance 1In general, it is possible, that s ≥ e. In this case, no substitution is performed. between two silhouettes is large, we can say that those silhouettes are not similar.
Due to this, we plan to only use the time series
comparison methods from the beginning of this section on those
reference silhouettes, that yield small histogram distances.
Further on, we will evaluate if the position determination
method presented in [
In this work we presented a new approach to motif recognition based on silhouettes on the example of mountains. Our method consists of three steps, of which the first two have already been implemented while we are working on the third step. First results show that we are able to extract silhouettes with relatively few errors from images and that our outlier detection step does indeed find meaningful anomalies. We have currently tested the first two steps of our approach as described in sections 3.1 and 3.2 on 18 images from the reference dataset. Results for the first of these images can be seen in figures 2 and 4. Of these 18 images, 17 result in good silhouettes, i.e. silhouettes with relatively few outliers of which most get marked and are correctable. The last image, though, does not get recognised correctly due to low contrast in terms of brightness. This is illustrated by figure 6. We do, however, notice this, because most of the silhouette gets marked as outlier.
The next step is to implement a silhouette matching
algorithm. This has already been outlined in section 3.3. Of
course, it is necessary, to benchmark the parts of that step
in order to find weaknesses early on. Once the system is
complete we aim to evaluate it on the whole of the dataset
of [
We also aim to create a mountain recognition corpus of our
own since [
Another interesting perspective is to test, whether our framework will work on other types of images, such as city skylines or pictures of single buildings. With these tasks the method itself could be quite similar, since skylines and buildings are mostly photographed with the sky as background, too. Furthermore, we aim to test our method on more diverse areas, such as the recognition of certain objects in MRT screenings or X-rays. These tasks will make it necessary to change some parts of our approach, naturally, because there, it will be interesting to be able to tell, for example, which organs are shown in a picture, or, as a next step, to be able to identify different kinds of tumours automatically.