2.1. What is a Landmark?

A landmark can be defined as any object or feature, which is easily recognisable, such as a monument or a building. Landmarks are one of the interests of tourists, most often due to notable physical features, cultural references or historical significance. People often use landmarks for casual navigation, such as when giving directions verbally or when sketching a route map.

In urban studies as well as in geography, a landmark is furthermore defined as an external point of reference that helps orientation in a familiar or unfamiliar environment (Lynch, Reference Lynch1960). As noted above, landmarks are also used in verbal route instructions. These two properties of landmarks (i.e. being used as references to orient objects and being used in verbal route instructions) are very important and potentially helpful in providing more desirable navigation services.

Landmarks can be geometric shapes, and they may include additional information (e.g., in the form of bar-codes, QR Codes and geo-tags). In general, landmarks have a fixed and known position, relative to which users can localise themselves. Landmarks should be carefully chosen to be easy to identify; for example, a large building has priority over a small one. A feature, which has significant contrast to the background, is a good option to be considered as a landmark since its image would be easily recognisable to users. Such objects have to possess a certain saliency, which makes them remarkable and distinctive. So the surrounding area determines the characteristics a point must have to be perceived as a landmark (e.g. a shopping centre may not be very outstanding in urban areas, but becomes a salient landmark when being situated in a rural village).

After extracting and storing important features as landmarks, it is possible to provide an image-matching service for positioning purposes. The next subsection is focused on landmark-based localisation.

2.2. Use of Landmarks in Image-Based Positioning

Positioning is one of the most important components of any navigation system. Pedestrians need a seamless indoor and outdoor positioning service, so the system needs reliable and accurate positioning techniques in the situation where signals from Global Navigation Satellite Systems (GNSS) are not available. Unlike cars, pedestrians can easily enter buildings; so an ideal navigation system should work seamlessly indoors and outdoors. This paper discusses a landmark-based positioning technique, which can be implemented as a seamless indoor/outdoor positioning solution, since landmarks are available indoors and outdoors.

In general, two main categories of positioning techniques, which use landmarks as reference points, can be imagined; image-based and non-image-based techniques. Some examples of image-based landmark positioning are Quick Response (QR) Code-based positioning and photograph-based positioning. Examples of non-image-based positioning are Radio Frequency Identification (RFID) and Bluetooth network positioning.

This paper focuses on image-based landmark positioning techniques, since most mobile phones are now equipped with cameras so hardware requirements are fewer. RFID tags and Bluetooth networks are not available ubiquitously, therefore hardware needs to be embedded and installed both on users' handheld devices (e.g. RFID readers) and also on the landmarks (e.g. RFID tags). This means extra costs for both service provider and users. In addition, in most image-based positioning approaches the computation and processing phase is done on the server side so such approaches have lower power consumption in comparison with Bluetooth positioning and similar techniques where users need to keep their mobile phones' Bluetooth on all the time. In addition, many landmarks are registered as tourist and/or historic features. Consequently, it is almost impossible to install or affix a tag or any signal transmitter for positioning purposes. Landmarks can be huge objects; therefore a single tag or transmitter cannot represent its accurate location. Being much cheaper, having less power consumption and possessing the ability to be used on readily available mobile devices may make image-based positioning more accepted by users.

This paper uses an image-based technique for positioning which applies a feature-matching engine to identify landmarks of which users have taken photographs.

Users can take a photograph of a registered and previously stored landmark and then send/upload it for image processing and feature matching. The feature-matching engine can extract and identify the landmark of which the photograph has been taken. To do so, image processing, feature extraction and feature matching techniques are applied. In addition, the uniqueness of landmarks hugely improves the accuracy of feature matching results. Also, for each registered landmark, there is a QR Code generated and affixed nearby or on the landmark that can be scanned (or even photographed) by the user; in the case that the feature matching service cannot accurately detect the landmark due to existence of a similar object in another area or high number of requests, the QR Code can limit the area of search for the feature-matching engine (Basiri et al., Reference Basiri, Amirian and Winstanley2014b). This backup method helps the engine to provide better performance. Then scale and rotation (tilt) of the photograph can be calculated, since the absolute sizes of different façades of the landmark have already been stored in a database or can be measured from the images in the database. Based on scale and rotation, the vector representing relative location of the user with respect to the landmark can be calculated.

Positioning of a user based on a camera positioning system generally has two main steps; image processing to identify the landmark and finding scale and rotation. The photograph taken by the user is processed to find a landmark. In this step the uniqueness of landmarks makes it much easier to find matching images in the database. Then, using the actual size and shape of the corresponding landmark, which has been stored in a database, it is possible to calculate the scale and rotation of the photograph taken by the user. This piece of information is used to calculate the user's relative position with respect to the landmark. Since absolute positions of landmarks are available in the database, the absolute position of the user can easily be calculated and then used in path finding and navigation services.

2.3. Use of Landmarks in Path-finding Algorithm

In order to find the shortest path between two points, path finding algorithms look for the minimum distance traversed. To find the fastest path, the route with minimum time is preferable. In pedestrian navigation the shortest path and the fastest path algorithms usually have similar outputs, as there is generally no traffic factor for pedestrians and they move with almost unchanging speed. It is, however, possible to consider other parameters for path-finding and so get different results. For example, in the case of users not being familiar with the environment, they may look for the most reliable path rather than the shortest one. Taking the most reliable path may reduce the chance of getting lost. In addition, most tourist navigation application users want to see specific monuments and landmarks, which may need deviation from the shortest path. A landmark-based path-finding algorithm provides a more attractive and, at the same time, more reliable path. Since users see more landmarks on the way, they get less bored and they are also more certain that they are taking the correct route.

Landmark-based path-finding identifies the path which traverses the least distance to get to the destination while passing the most landmarks on the way. So landmark-based path-finding algorithms are trying to maximise the result of:

(1)$$Number \; of \; landmarks \; of \; each \; edge\; / length \; of \; that \; edge.$$

The same shortest path algorithm can then be implemented but the cost or distance, which is usually called weight and supposed to be optimised, will be replaced by the value of Equation (1) (i.e. number of landmarks/length of each edge).

Based on the landmark-based path-finding algorithm, once the route is calculated it is then possible to provide users with navigational instructions, which includes pictures of landmarks to be seen on the way.

2.4. Use of Landmarks in Navigational Instructions

As mentioned previously, landmarks can help to make navigational instructions approximate more closely the instructions that people give in their daily conversations. One of the best ways to use landmarks in navigational instruction is to provide images of landmarks as a part of the instructions at or near key points, such as turning points and important cultural or heritage features (landmarks).

For each key point in the calculated path (junctions or landmark to be seen), the direction (d) between the current key point or user's position (indexed i) and the following one (indexed i + 1) is calculated using Equation (2).

(2)$$d = \pi /2 - \arctan _2 (lat_{i + 1} - lat_{i}\comma lon_{i + 1} - lon_i )$$

Then, the image with the closest camera position from the key point i and the closest heading from d is retrieved. The landmark database is queried to retrieve a sequence of landmarks (position of camera when images were taken) from the desired path in the direction the user should take to reach the destination. Then based on these points, images are retrieved from the file system and then images are augmented by overlaying a 3D arrow pointing at the following direction to take, helping the user to visually interpret his or her position and get their bearings. The service uses two services behind the scenes:

• • Simple image retrieval: This service takes geographical coordinates as an input and returns the URL of the image with closest registered coordinates within the database.

• • Image sequence retrieval with visual navigation information: This service takes two GPS coordinates as an input, calls the path-finding service to get the best route between the two given positions, and returns the sequence of images from the database taken along this path using the Simple image retrieval service. Finally, the images are augmented with a 3D arrow pointing at the next direction in the path.

The implementation details of augmented reality functionality are described in the next section.

For each point of the calculated path, held in KML format, the direction d between the user's current position (indexed i) and the following key point (indexed i + 1) is calculated using Equation (2). Then, the image with the closest camera position from the point i and the closest heading from d is retrieved. To find the mentioned image, a score value s is calculated using location and heading from the Euclidean distance, which can be between 0 and 1 (Amirian et al., Reference Amirian, Basiri, Gales, Winstanley and McDonald2015). A sigmoid function is used to set to a score close to 0 for near images and 1 for the others. A trigonometric function is used to get a similar score for the heading (Equation (3)):

(3)$$s = (1 - s_{pos} )(1 - s_{head} )$$

In the above formula, the s _pos is the score given by the Euclidean distance p between the position of the point and the position of image (Equation (4)):

(4)$$s_{pos} = 1/(1 + e^{( - 2.25(\,p - 15))/5} )$$

The constants of the Sigmoid function are set experimentally, representing the threshold distance from which it is possible to exclude the results as “they are too far away and cannot be a match”. Figure 2 shows a plot of this function. The higher the distance p is, the higher the cost is.

Figure 2. Position cost function where p is the Euclidean distance between the point positions (in the path) and the image camera position.

The heading score s _head is calculated by Equation (5):

(5)$$s_{head} = \vert\sin (h_{cam} + d)\vert$$

Figure 3 shows a plot of this function. The higher the angle difference between the camera heading hcam and the heading direction d, the higher the cost is.

Figure 3. The heading score is high when the angle difference between the image camera heading and the heading direction d is high.

As is shown in this section, landmarks can be used for localisation, path-finding and navigational instruction.

3.1. Landmark Extraction

Landmarks have to possess a certain saliency, which makes them remarkable and distinctive. To decide which features can be stored as landmarks the project team members, as experts in urban planning, identified and short-listed the landmarks on the campus. Selected features, as landmarks, are stored in a spatial database as spatial objects with some attributes such as importance, type, name, etc. Landmark extraction and storage can be done automatically using the different criteria, algorithms and approaches discussed before.

In order to find and extract important features on the campus to be stored in the database as landmarks, three criteria were considered: uniqueness; contrast with surroundings; and size. Figure 4 shows one of the most important landmarks on the NUIM campus, extracted from a 3D model of the campus, which is the highest and the most unique feature and as such can be seen from almost everywhere on the campus.

Figure 4. Landmark extraction from 3D model of NUIM campus.

In order to select landmarks, one of the best approaches is comparing the attribute values of data records (e.g. size, colour, types, building labels, etc.) and identifying the most suitable landmark by ranking all attributes at potential decision points, as proposed by Elias (Reference Elias2003). The only problem in this approach might be that it disregards the fact that the visibility of an object is not invariable and that the quality of a landmark can differ depending on the direction from which it is viewed (Brenner and Elias, Reference Brenner and Elias2003). In order to address this issue, the visibility of each feature should be calculated using a Digital Surface Model (DSM) of the campus, which can be found from the 3D Campus project (Figure 4). Features, which can be viewed from long distances, are considered as suitable landmarks based on which we can provide landmark-based navigational instructions.

Knowing the user's height and the height of each landmark to be seen, it is possible to calculate whether or not the landmark is visible from the user's point of view.

Seeing a bigger part of a landmark increases the certainty and confirms that the user is on the correct path. Equation (6) shows the visibility of an object. If there is no intervening object that acts as an obstacle, then you can see the landmark 100% and if the intervening object is as high as the landmark then (L ₂ − H)/L ₂ is zero and you cannot see it. Thus (L ₂ − H)/L ₂ is a factor that shows the visibility of a landmark.

(6)$$(L_2 - H)/L_2 *((D_1 *L_2 + D_2 *L_1 )/(D_1 + D_2 ) + 1)$$

where L ₁ is user's height and L ₂ is the height of the landmark to be seen. H shows the height of the intervening object and D ₁ shows the distance between the user and the intervening object. D ₂ is the distance between the intervening object and the landmark to be seen.

Assuming L ₁ to be approximately 160 centimetres, the average human height, it is possible to calculate the visibility of each landmark from users' point of view. This is used to provide information on landmarks, which can be seen from the users' point of view, as a part of the navigational services.

For each landmark, the edge(s), size and shape are also stored. These attribute values are applied by the landmark-based positioning component to calculate scale and rotation of the photograph taken by the user.

3.1. Landmark-based Navigation

Using landmarks stored in the spatial database, it is possible to find the best path and navigate users to their destination. The architecture used to provide the user with landmark-based navigational instructions is illustrated in Figure 5. The landmark-based navigation system implemented in the National University of Ireland consists of four main components; positioning component, data and service database, navigation service calculation engine and users and their mobile devices.

Figure 5. High-level conceptual architecture of eCampus applications.

The positioning component is responsible for calculating the position of the user using GPS or image-based positioning techniques, which were explained previously, and also for tracking them. It delivers its output, position of the user, to the navigation service calculation engine.

The navigation service calculation engine uses the user's position as an input for two other services; firstly, it calculates the best path using the user's position and selected destination, and secondly, based on the user's position, it can calculate visible landmarks on the way. In order to do both of these tasks, the navigation service calculation engine needs to have access to the spatial database where landmarks' information, such as location and size, is stored. In this project, a graphical database is used.

In general, elements in a landmark-based navigation service change with quite a high degree of frequency, since landmarks can be visible from one user's position but not from another's. Processing of such highly connected and interrelated data can be problematic for most conventional and modern storage systems such as Relational Database Management Systems (RDBMS). By nature, navigation services need to be highly responsive in real time or near real time. In addition, since there are usually a large number of users, such services must provide appropriate scalability and performance measures (Amirian et al., Reference Amirian, Basiri and Winstanley2014). Also, some of the network processing technologies process widely used network analysis and store these results beside the network data itself. However, when additional network elements (such as new landmarks or new roads) have to be added to the data, the previously built network must be rebuilt and recompiled. This recompilation process would be a serious processing task, especially when the newly added elements have lots of connections to the existing elements. In order to avoid such issues, it is better to store connected data in their natural representation and this is where the graphic database can come into play.

The navigation service calculation engine uses landmarks, edges and nodes data to find a more reliable path. This is calculated based on the landmark-based path finding algorithm explained in previous sections. Figure 6 shows one of the calculated routes; as is shown, some parts of calculated route pass through buildings. In order to calculate the user's position inside the building, image-based positioning is used since there are some stored indoor landmarks as well.

Figure 6. Navigation services in eCampus web application.

Once the route has been calculated, the user should be provided with navigational instructions to follow the calculated route. In this step, the navigation service calculation engine uses positional information provided by the positioning engine and also data stored in the database such as information on landmarks to calculate the landmarks to be seen from the user's location. Whenever the user's location changes or they request a new image-based positioning solution, this process will be repeated and a new set of navigational instructions is provided.

In Figure 6, the map on the user's screen is shown. As it illustrates, some of the landmarks are located outdoors and the rest are located inside. Upon reaching each landmark, related information is delivered to the user.

Since the navigational instructions contain some information about landmarks, which can be seen from the user's point of view, this approach may be more compatible with tourist navigation applications. In addition, users feel that it is less likely that they may get lost, since they are being provided with pictures of landmarks, to be seen shortly. So they are reassured that they are on the right path.

3.2. Providing Navigational Instructions using Landmarks

In order to provide image-based navigation instructions, a web service was developed which takes two coordinates as an input; current location (or origin) and destination. It then calls the path-finding web service to obtain the pedestrian path between the two given positions, origin and destination. Next it queries the path-finding service, and parses the KML response to find landmarks to-be-seen on the way. Figure 7 shows screen shots of the user's device showing visual navigational instructions.

Figure 7. Visual navigational instructions in eCampus web application.

The landmark-based navigation service takes advantage of the geolocation capabilities of mobile devices and/or HTML5 geolocation API and uses the pedestrian navigation web service in order to provide visual navigation on the NUIM campus. The position of the user is retrieved from the GPS of the mobile device or a QR Code affixed to each turning point or geolocation API (or manually selected by the user) and a desired destination is selected. The path between these two positions is retrieved using the pedestrian navigation web service. Then a spatial database of images of the campus is queried to retrieve a sequence of points (position of camera when images were taken) taken from the desired path in the direction the user should take to reach his destination. Then, based on the points, images are retrieved from the database and augmented by overlaying a 3D arrow pointing at the next direction to take, helping the user to visually interpret his position and get his bearings. Two services are used behind the scenes:

• • Simple image retrieval: This service takes geographical coordinates as an input and returns the URL of the image with closest registered coordinates within the database.

• • Image sequence retrieval with visual navigation information: This service takes two GPS coordinates as an input, calls the pedestrian navigation web service to get the pedestrian path between the two given positions, and returns the sequence of images from the database taken along this path using the Simple image retrieval service. Finally, the images are augmented with a 3D arrow pointing at the next direction in the path.

The whole process of positioning and retrieval is 800 ms, on average. The spatial database is implemented using PostgreSQL/PostGIS. Table 1 illustrates the schema of data in the spatial database.

Table 1. Schema of image data table.

In order to capture images, a native mobile app is implemented which captures images along with the coordinates and heading of the mobile device. Then another script is used to upload data from the mobile device to the spatial database on the web server, as well as to transfer the images to a public directory on the web server.

Simple image retrieval is implemented using php-scripting language. To use this service a GET request can be sent to its URL with the latitude and longitude parameters (a geographical position). It returns a JSON string with the URL of the retrieve image in the public directory.

If no image can be found, it returns a 204 HTTP status code which means “No Content” is available.

The web application of image-based NUIM campus navigation services is available on http://147.252.87.12/eCampTest/Routing/ and the web application of image retrieval is available on http://ggalessrv.cs.nuim.ie/eCampus/public_scripts/imnav.html.