Navigation Tool for Identification of Jewish Tombstones in the field
Idea
The idea behind this project was to create a powerful, multifunctional and yet user friendly Android app. It should provide all the basic tools to help the user navigate through a "off road" area - in our case a Jewish cemetery in Worms, using built in GPS and GSM modules along with a customised map. Additionally, we wanted to equip the user with a set of tools which would allow him to identify the graves, both using built-in smartphone camera - comparing the camera view to the tombstones' pictures in the database - and by displaying a detailed 3D model of the tombstone.
Features
The application has three main features: GPS navigation, camera recognition and 3D model view.
GPS navigation
It's the basic functionality that helps the user navigate through the cemetary. It basically consists of a map view, with user's position marked with a blue dot and a number of navigation options accessible through the menu. When the user chooses to navigate to a particular tombstone, it's position is displayed on the map. Simple, yet very useful option - especially considering the number of graves on the cemetery and lack of other tools that provide GPS functionality in the areas without roads.
Camera recognition
While the GPS navigation is pretty accurate, often many graves are located within a couple of meters from each other. That's why this application features camera comparison functionality, which allows the user to simply point the smartphone camera at the tombstone, take a picture and then let the app compare it to all the tombstones in the database within a reasonable distance. Feature detection chooses 5 best matches from the database and displays them on the screen.
3D model view
Many tombstones have already been scanned with a 3D scanner - so the app also has the ability to display those 3D models. Although an external application is used for that purpose, everything is accessible through the app and does not require any further actions beside choosing the corresponding option in the menu. There is of course a set of standard tools available, providing user the ability to rotate the model, zoom in and out and change the lighting (very useful when reading the writings on the tombstones!).
Design
The following class diagram show the main classes we have created:
The class DatabaseHandler is used to create a SQL Database to manage all graves and the data that belongs to each of them like picture destination and GPS position.
The main class of our app is MainActivity. This activity is started when the user starts the app. All navigation processing is done here. There are also functions to show the main menu of our app. In the main menu the user have two options to get some knowledge. The first option starts to navigate to some specific grave and the user get some information about it and the second one starts the camera feature detection so the user can get some knowledge about the graves nearby.
The class FeatureFinder is used in the MainActivity to start the one other activity FeatureResultActivity. The class has two main functions. One function for comparing two images with feature detection algorithm. The other function also compares two images, but also create a view which shows the two images and connects good matching points.
The class FeatureResultActivity is used to start the feature finding process for a number of tombstones with a low distance to the user position. Also the result view ,that is created after the feature finding process have ended, is defined in this class.
Implementation
The following implementation details of our app are important to know.
OSMDroid library
For the navigation part of our app, we needed a tool to display custom maps. The standard Android built-in map viewer is useful to display Google Maps, but we only had an PDF file of the map. The OSMDroid library is perfect for our requirements, because it provides the functionality of displaying custom map tiles and also includes overlay support like icons for specific locations. So we can load our custom map tiles with the library and we use the supported icons to display the current user position and the destination of the chosen gravestone.
Standard Android features
The first Android feature (or limitation, to be precise) you should know is that Android restricts the compressed file size (10MB). The map file we've created was bigger than 10 MB size. Therefore you have to manually copy the map on your device.
Android also have some build-in apps like the camera app that we used. So you do not have to change manually from the our to the camera built-in app. We start the built-in camera app with our app and after the user has taken a picture, the picture is used in our app for the camera recognition feature.
There is also the possibility with Android to start every other app on your device. We use this feature when we start the external App for displaying the 3D models of the graves. Android automatically looks for the suitable app if you want to open a specific data type. For example with an email address as input Android will searches for an email app on the device and let the user choose one of the apps that can handle email adresses.
OpenCV library
The image comparison is most complex part of our app. We used functions of the OpenCV library to add this functionality. The OpenCV library contains a lot of functions for image processing and object recognition. For the feature detection the most common feature detection algorihms are already implemented, except the patented ones. Because the best feature matching algorithms (SIFT and SURF) are patented, we have used the best alternative (ORB).
Problems
Of course, we had many problems while developing this application. While many of them were quite boring and easy to solve, we find some of them particularly worth mentioning.
The first difficulty occurred when we were trying to create a custom map for our application. While there is a lot of software created for the sole purpose of creating custom map tiles, it is quite difficult to find one that would suit all our needs. Finally, we decided to go with Map Tiler, which created quite good map tiles, however in the wrong naming convention. We had to use a custom written script to rename all those files (over 2000 .png files) every time we had to create a new version of the map - and the latest one is number 23!
That was however just the half of our map problems. After creating out first working map, we faced a hardware based issue - Android devices are not equipped with enough memory to process such a big map. After trying different tile formats, changing configuration options in the Map Tiler, dealing with memory management configuration in Android - the solution turned out to be very, very simple - we had to change the tile format in the OSMDroid library, that we used for displaying the map - to the format we are NOT actually using! One line of code - works like a charm.
The other problem that occurred on the way was the configuration of OpenCV library used for comparing images. Tombstones are quite specific objects, not to mention the fact that the surroundings is changing (grass grows, trees are cut, people put stones on the top of the tombstones) - all that makes it quite difficult to find the right set of options. Solution? Well, a long, long time that we spent on the cemetery, testing the app and changing the configuration on the spot. Interesting remark here - comparing two high quality pictures made with an iPhone instead of comparing picture from an Android phone to the one in the database gave far better results. That actually leads to the conclusion, that with better phone cameras and perhaps improving the quality of images in the online database - the problem will eventually solve itself.
The other problem with OpenCV we had, were the lack of documentation especially in the Android environment. The use of OpenCV in C++ is well documented, but Android apps normally are written in Java. The difficulty is that the feature detection algorithms can handle only special data types. After long web research we finally get the knowledge for using the right OpenCV image data type and how to transform the camera image data type into this type. Also the right combination of feature descriptor to feature matcher was not easy to find.
Improvements
Every piece of software can and should be constantly improved. Here are some ideas that we have:
Augmented reality
It would be quite interesting to completely change app's design and integrate it with a camera view. Navigation tips would be displayed in a form of arrows pointing in the right direction, every other functionality could be simply accessible through a pop up menu. The added bonus here would be the fact that constant analysis of camera image could improve GPS navigation accuracy.
iOS
As our app works exclusively on Android devices, it would definitely be a good idea to port it to iOS devices as well. Plus, with noticeably better GPS performance of Apple devices and more powerful hardware, there's quite a good chance that the application would work even better.
Q&A
Would it be a good idea to use built in accelerometer and gyro to determine in which way the device is pointed and narrow down the possible tombstones for camera recognition to only those actually pointed in that direction?
It would actually be a great idea! The only problem is - most of the tombstones in a certain area are pointed in the very same direction. As we are already choosing only those within a couple of meters, we would normally eliminate at most one or two tombstones.
Would it be possible to make an off-line version of the app?
It certainly would - the database, photos, 3D models would however require a separate SD card to store them.
Have you considered storing just the set of points for every tombstone in the camera recognition function instead of the whole photograph?
That's an excellent idea. This approach would also minimize the file size of a picture. But everytime you change the feature detection algorithm, you need to recompute this special feature points for every picture to get good results.
About Us
| Name | Subject | Semester number | Other information |
|---|---|---|---|
| Clemens Maier | Computer Science, M.Sc. (Master Informatik) | 2.Semester | |
| Szymon Kózka | Computer Science, B.Sc. (Bachelor Informatik) | 6.Semester | ERASMUS student from Warsaw University of Technology, Poland |