Walk line drawing

Walk line drawing BACHELOR’S THESIS submitted in partial fulfillment of the requirements for the degree of Bachelor of Science in Computer Science by Pablo Balduz Registration Number 1635296 to the Faculty of Informatics at the TU Wien Advisor: Ivan Viola Vienna, 25th April, 2017 Pablo Balduz Ivan Viola Technische Universität Wien A-1040 Wien Karlsplatz 13 Tel. +43-1-58801-0 www.tuwien.ac.at Erklärung zur Verfassung der Arbeit Pablo Balduz Medwedweg 3, 1110 Wien Hiermit erkläre ich, dass ich diese Arbeit selbständig verfasst habe, dass ich die verwendeten Quellen und Hilfsmittel vollständig angegeben habe und dass ich die Stellen der Arbeit – einschließlich Tabellen, Karten und Abbildungen –, die anderen Werken oder dem Internet im Wortlaut oder dem Sinn nach entnommen sind, auf jeden Fall unter Angabe der Quelle als Entlehnung kenntlich gemacht habe. Wien, 25. April 2017 Pablo Balduz iii Acknowledgements First of all, I would like to express my sincere gratitude to my advisor Ivan Viola for giving me the opportunity to work on this Bachelor thesis at the Institute of Computer Graphics and Algorithms from Technische Universität Wien. I really appreciate all the counsel given in our weekly meetings, as well as his predisposition to help in any aspect related to the project. Furthermore, I am really thankful to my friends and family for their support during all my studies and especially during my stay in Vienna working on this thesis. v Abstract In the recent years, consequence of technology improvements, a new kind of art has appeared. It is called GPS art and consists in drawing on a digital map by recording the path followed using a GPS device. The fact is that not everyone is able to make the drawing of a certain figure. Just the so-called GPS artists come up with the path, so it makes this kind of art not reachable to some people. The idea of this thesis is to enable people to create GPS art without relying on imagination to come up with a path for a certain figure. In order to achieve that, a system that finds that path in a map for a given figure as input has been developed. In order for people to use this system, it has been integrated within a mobile application, so users are able to find the path to follow easily. vii Contents Kurzfassung vii Abstract ix Contents xi 1 Introduction 1 1.1 Motivation .................................. 1 1.2 Methodological approach . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Structureofwork.............................. 3 2 State of the art 5 2.1 Sportsapps................................. 5 2.2 Imageregistration ............................. 6 3 Method 11 3.1 Imagecomparison .............................. 11 3.2 Remapping ................................. 14 4 Implementation 17 4.1 GoogleMaps ................................ 17 4.2 OpenCV................................... 18 4.3 Android.................................... 21 5 Conclusion and outlook 23 5.1 Summary and critical review . . . . . . . . . . . . . . . . . . . . . . . 23 5.2 Futurework................................. 24 List of Figures 25 Glossary 27 Acronyms 29 Bibliography 31 ix 2. State of the art 2.2 Image registration Image registration is the process of establishing the spatial or temporal correspondence among data sources. This data may be multiple images acquired at different times and/or with different modality. It is used in computer vision, medical image, automatic target recognition and in the analysis of images and satellite data. The registration is necessary to be able to compare or integrate the data obtained from these different measurements. [2] [3] In image registration there are normally four steps. First, a sufficient number of control points are required in order to estimate an optimal geometric transformation between two images (feature detection). After that, feature matching is necessary to find corresponding points because many feature points may be extracted from one image but not from the other. Then a transformation function is used to model the geometric relationship between the two images and finally, the unknown parameters of the function can be computed according to the control points. [4] Among data images, one of them is known as the reference and another image is known as the target. Image registration is a process of finding the spatial transformation of the target image to align it with the reference image and there are two fundamental approaches to achieve this transformation. Intensity based methods compare the intensity patterns in the images through correlation metrics, whereas feature based methods find correspondence between image features, such as points, lines and contours. Intensity based methods register complete images or sub-images. If sub-images are registered, centers of the corresponding sub-images are considered as corresponding feature points. Feature-based methods establish the correspondence between several points in images. Knowing the correspondence between several points in the images, a transformation is determined to map the target image to the reference images, establishing point by point, the correspondence between the reference images and the target. Image registration algorithms can also be classified according to the transformation models that they use to relate the target image space to the reference image space. Rigid transformations are the simplest category; it includes linear transformations, which are translation, rotation, scaling and other affine transformations. Linear transformations are global in nature; therefore, they cannot model local geometric differences between images. Apart from rigid transformations, there is another category that allows elastic or non-rigid transformations. These transformations are able to locally deform the target image to align it with the reference image. Non-rigid transformations include radial basis functions, continuous physical models and large deformation models. An example of transformation, which is in fact important in this project, is the distance transform. A distance transform is a derived representation of a digital image, normally only applied to binary images. Each pixel of the image is labeled with the distance to the nearest obstacle pixel. A most common type of obstacle pixel is a boundary pixel, which 6 2.2. Image registration means a different value pixel, in a binary image. The result of the transform is a gray level image that looks similar to the original one, except that the gray level intensities of points inside foreground regions are changed to show the distance to the closest boundary from each point. [5] [6] Figure 2.1: Example of how pixel values are assigned in a distance transform. [5] A representation of the example above is the following: (a) Original image. (b) Distance transform image. Figure 2.2: Example of the distance transform applied on a binary image. [6] While the predominant number of approaches is performed in the spatial domain, there are a few approaches that transform the data into frequency domain to solve a particular registration task. Spatial methods operate in the image domain, matching intensity patterns or images characteristics. Some of the algorithms that match characteristics are derivations of the traditional technics of manually registering an image, in which an operator decides the corresponding control points in the images. When the number of control points exceeds the minimum required to define an appropriate transformation model, the iterative algorithms such as RANSAC (Random Sample Consensus) can be used to robustly estimate the parameters of a particular type of transformation in image registration. Methods in frequency domain find the transformation parameters for the image registration while working in the transformation domain. These methods work by simple transformation, such as translation, rotation and scaling. For example, 7 2. State of the art applying the phase correlation method to a pair of images produces a third image, which has peak intensities at locations where the two images math the best. The intuition behind this method is that the resulting image will have the maximum peak value when the contents of the images math up exactly and that peak location correspond to the relative translation between the images [ 7 ]. Unlike many algorithms in the spatial domain, phase correlation method is noise, occlusions and other defects typical of medical or satellite images, insensitive. Besides, the phase correlation uses the Fast Fourier Transform to calculate the cross-correlation between the two images, which results in great performance improvements. This method can be extended to determine the rotation and scale differences between two images. Another classification can be made between monomodal and multimodal methods. Monomodal methods register images in the same modality acquired by the only type of scanner/sensor, while multimodal methods tend to register images obtained by different types of scanners/sensors. Multimodal registration methods are often used in medical imaging since the images of a patient are obtained by frequency from different scanners. Registration methods can be classified according to the level of automation they offer. There have been developed manual, interactive, semiautomatic and automatic methods. Manual methods provide tools to manually align images. Interactive methods reduce user bias by performing certain key operations automatically while still relying on the user to guide the registration. Semiautomatic methods make more registration steps automatically but they depend on the user to verify the correctness of a registration. Automatic methods do not allow user interaction and make all registration steps automatically. A measure of image similarity quantifies the degree of similarity between the intensity patterns of two images. The choice of a measure of image similarity depends on the modality of the images to be registered. The most common examples of image similarity measures include cross-correlation, mutual information, sum of squares of intensity differences, and image uniformity ratio. Cross-correlation, sum of the squares of intensity differences and image uniformity ratio are used for registering images in the same modality. On the other hand, mutual information and normalized mutual information are the most popular image similarity measures for multimodal images registration. An example of similarity measures application is shape matching. Shape matching is highly related to similarity measures because it deals with transforming a shape, and measuring the resemblance with another one using some similarity measure. So, shape similarity measures are an essential ingredient in shape matching. [8] 2.2.1 Applications Image registration has applications in remote sensing (cartography update) and computer visions. Because of the many applications to which image registration can be applied, it is impossible to develop a general method that is optimized for all uses. Registration of the medical image (for data from the same patient taken at different times, such as the detection of changes or control of a tumor), often also involves elastic 8 2.2. Image registration registration to make face deformation of the patient (due to breathing, anatomical changes and so on). The non-rigid medical imaging record can also be used to record a patient’s data for an anatomical atlas. It is also used in astrophotography to align images taken from space. Using the control points, the computer performs transformations on an image so that the main features are aligned with a second image. Image registration is an essential part of creating panoramic images. There are many different techniques that can be implemented in real time and run on integrated devices such as cameras and camera phones. 9 CHAPTER 3 Method The developed system finds in a map of pedestrian-accessible areas a path that makes a desired visual pattern depicted as a simple line drawing. The algorithm consists of two major stages: one is the image comparison made through registration and the second stage is the remapping of the figure desired to represent onto the map. 3.1 Image comparison In the first part of the algorithm, the comparison between both, the map and the figure image is made. The outcome of this stage is to generate a new gray scale image in which each pixel is labeled with a different level of intensity. The lowest intensity value areas of the new image (that means the darkest parts) encode a higher probability to find a representation of the figure in that area. This stage can be understood as a similarity evaluation. The comparison is applied on two bitmap images: one is the figure intended to be found in the map represented as simple line drawing as showed in Figure 2.2 and the other one is the map. This map image is obtained from Google Maps but getting an image from the default map that appears in the Google Maps application to use in the comparison would be useless. That map has many different colors, shapes, names of streets, roads and places that would introduce many errors during the similarity evaluation as we might be comparing pixels of the figure with pixels of the name of a certain street. To solve that, a new map in which only the street layer remains visible and in which there are not different shades or colors must be generated and it is done via the Google Maps Application Programming Interface (API). Using the Google Maps API by following the steps described in Chapter 4, we are able to generate a map with the described features, shown in Figure 2.2. 11 3. Method (a) Sample figure that could be used in the comparison. (b) Generated map using Google Maps API. Figure 3.1: Example of a sample image and map that could be used in the algorithm. The comparison is not directly made over two images like the ones above, comparing two bitmaps would be very sensitive. Unless the figure perfectly matches some area in the pattern of the street layer, the differences would be very high. Even if the alignment between the figure and the street layer is nearly perfect, at the moment in which a pixel of the figure and a pixel of the map that does not correspond to any street are compared, it will result in a high difference as well. To solve this undesired high sensitivity of the similarity transform generated in this stage, instead of a bitmap image of the map we use its distance transform image like the one in Figure 3.2b. This way, during the similarity evaluation, even if the alignment between the figure and the street layer is nearly perfect, it will result in a high similarity score due to the much lower difference between the images being compared, which is the desired behavior for a nearly perfect aligned figure. The distance transform allows to better obtaining a measure of how close the figure being compared is to the each street in the map grid, as each pixel in the new map indicates the distance to its nearest street. (a) Gray scaled map. (b) Map’s distance transform. Figure 3.2: Example of the distance transform applied on a gray scaled map previously generated. After the similarity evaluation, a new image bitmap is created. As already explained, 12 3.1. Image comparison each pixel of this new image indicates the similarity level of the figure at the position indicated by that pixel. A low pixel value, which corresponds to the dark parts, means a high similarity score. This image is obtained as a result of the comparison of the figure image all over the map distance transform. During the whole process, the figure image is centered on each pixel of the map distance transform so that the figure image fits in the map and the comparison is carried out, that is to say, the figure image is not centered on pixels in which part of the figure would remain out of the map image bounds because there would be a part that could not be compared. It makes no sense to compare part of the figure because the aim of this comparison is finding a representation of the whole figure. During each comparison, the computed value is assigned to a new image that will correspond to the result similarity image. If the figure image is centered over the map distance transform and iterates all over it row after row starting on the top left corner, the new image should be filled following the same directions, row after row in this case. In the end, the similarity image dimensions would be the difference between the figure and map image dimensions. The similarity image pixel values are obtained by comparing both the figure image and the corresponding part of the map distance transform. In this comparison the positions for black pixels in the figure are taken and used to obtain the values of the pixels corresponding to the figure in the distance transform. For each of the figure pixels we now have a value that indicates how far they are to their closest street in the map image and by computing the sum of those values we have an indicator of how close the figure is to its representation on the map streets. The higher this value is, the worse the similarity as it indicates that the figure is far from being represented in the street layer. After assigning every value to the new bitmap, we may have an image like the one in Figure 3.3. The darker parts indicate high similarity score as already said. If the image generated is too uniform that nothing can be distinguished, we can vary every pixel intensity until much more differentiated areas appear. Figure 3.3: New gray scale similarity image obtained from the comparison between the map distance transform and the figure. The comparison made so far only uses the figure image with the default orientation and 13 3. Method scale, but the figure may be found in the map with a different angle of rotation and size. In order to support that, it is necessary to add it into the comparison. In each iteration, the figure image is rotated and scaled so that the sum of the distance values is computed for every orientation and scale combination. At the end of the iteration the lowest value, which is the best result as previously described in this chapter, is used for the new image generated and stored with the corresponding orientation and scale. As well as the figure image may have different scales, so does the map. Nowadays, digital maps have different levels of scale; the more we zoom in on a map, the more streets appear on the screen and the more we zoom out on a map, the fewer streets we are able to see. This is appreciated in Figure 3.4 and means that the whole comparison described so far needs to be done for different map scales in order to cover a wider range. In fact, this improves the chances of finding the figure in the map. (a) Zoom level 1. (b) Zoom level 2. (c) Zoom level 3. Figure 3.4: Different zoom levels for a map. 3.2 Remapping The comparison between the images generates a new gray scale map indicating the parts where the chances of finding a representation of the figure are higher. After that, the remapping should be done; this means moving the figure onto the streets in the map grid and this is achieved using the distance transform map. For every position in the new gray scale image, besides the value there is information about the figure orientation and scale. This information is enough to do the remap. For a given position in the map, the corresponding figure image with its orientation and scale in that position is computed in order to obtain the positions for the figure black pixels. Then, the map distance transform image is used to do the remap. In the distance transform image, a pixel having a value of 12 means that this pixel is 12 positions (pixels) away from the nearest pixel that has value 0, which corresponds to a 14 3.2. Remapping street. Only with the distance transform there is no clue on which direction to follow to get to the pixel with value 0. As the distance indicated by the distance transform is the distance to the nearest cero value pixel, the direction to follow will be the one with greatest rate of variation and that is given by the gradient. So in order to find the direction to follow, the gradient in that pixel must be calculated. Once having the direction, the cero value pixel is just 12 positions away in that way (in this example). Following that process for every of the black pixels positions will lead to a bunch of new positions in the map which will correspond to the new remapped figure as shown in Figure 3.5b. (a) Map and figure overlayed. (b) Figure remapped. Figure 3.5: Example of the a figure remapping into a map for a given position. 15 CHAPTER 5 Conclusion and outlook 5.1 Summary and critical review This thesis began with a single idea: Try to represent a drawn figure in the streets map layer of a city in an automated way. After doing a preliminary research, nothing similar was found. Everything done until then was figures represented by artists that had come up with the path in a certain region. A first approach was carried out by comparing, both the image of the corresponding map and the figure. This comparison was made over the distance transform of the images. The results obtained were not that good as using the distance transform in both images, the number of dark pixels in the figure increase and the sums of pixel values differences along the map were pretty uniform. The second approach improved the results. Instead of using the distance transform of the map and the image, only the map one was used and only the black pixels in the figure were taken to compute the image with the sum of pixel differences. This made this image to have much differentiated parts, which is better. Regarding the implementation part, the first technology chosen to develop the algorithm was Matlabs but the results were not good at all. In terms of time consuming, it was really slow so it was decided to change to C++ and use OpenCV libraries. Time consuming improved a lot, although it is still slow due to the amount of calculations that are being made between the images. As a final reflection on this thesis, the main conclusion would be that the method performed is good as a first approach. The results demonstrate that the figure shape is more or less remapped onto the streets layer. This work has served to confirm that the initial idea was achievable and opens a new path in which it can be improved. 23 5. Conclusion and outlook 5.2 Future work The first approach of the system presented in this thesis opens a new path for improving it and adding new features. The algorithm developed focuses on the basics, which is translating a figure into the streets map layer without any conditions. The system treats every part of the map as equal, that is to say; for example, in a map a building, a square or a park may look similar (as an empty space) but this fact is not relevant for the algorithm. A next direction to follow could be somehow to penalize positions of the map weather they are walk able or not, so the remapping does not send the user over a building for example. In terms of performance, there is another way in which the system could be improved. Currently it takes a long time to do all the calculations, especially if the images used are big, so it would be a good idea to optimize it and lower the time of execution. A good direction to follow may be to use GPU computings. 24 List of Figures 1.1 ExampleofGPSart.[1]............................ 2 2.1 Example of how pixel values are assigned in a distance transform. [5] . . . 7 2.2 Example of the distance transform applied on a binary image. [6] . . . . . 7 3.1 Example of a sample image and map that could be used in the algorithm. 12 3.2 Example of the distance transform applied on a gray scaled map previously generated..................................... 12 3.3 New gray scale similarity image obtained from the comparison between the map distance transform and the figure. . . . . . . . . . . . . . . . . . . . . 13 3.4 Different zoom levels for a map. . . . . . . . . . . . . . . . . . . . . . . . . 14 3.5 Example of the a figure remapping into a map for a given position. . . . . 15 4.1 Steps to follow in order to use OpenCV in an Xcode project. [13] . . . . . 20 25 Glossary computer vision Interdisciplinary field that deals with how computers can be made for gaining high-level understanding from digital images or videos. From the perspective of engineering, it seeks to automate tasks that the human visual system can do. 8, 18 GPS art or GPS drawing is a method of drawing that uses GPS technology to create large-scale artwork. It combines art, movement, and technology. 1, 5 GPU computing Is the use of a Graphics Processing Unit (GPU), which typically handles computation only for computer graphics, to perform computation in applications traditionally handled by the Central Processing Unit (CPU). 24 Matlab (MATrix LABoratory) is a multi-paradigm numerical computing environment and fourth-generation programming language. 23 open source Decentralized development model that encourages open collaboration. Its main principle is peer production, with products such as source code, blueprints, and documentation freely available to the public. 18 Xcode Integrated development environment for macOS containing a suite of software development tools developed by Apple for developing software for macOS, iOS, watchOS and tvOS. 18, 19 27 Acronyms API Application Programming Interface. 11 BSD Berkeley Software Distribution. 18 GPS Global Positioning System. 1, 5 OpenCV Open Source Computer Vision. 18, 19, 21, 23 OS Operating System. 18 29 Bibliography [1] A. Gri. Artist draws world’s largest doodles by riding his bike with gps. [Online]. Available: http://www.boredpanda.com/bike-gps-doodle-stephen-lund/ [2] (2017, April). [Online]. Available: https://en.wikipedia.org/wiki/Image_registration [3] J. F. Barbara Zitová, “Image registration methods: a survey,” June 2003. [4] Z. X. . Y. Zhang, “A critical review of image registration methods,” International Journal of Image and Data Fusion, 2010. [5] (2016, March). [Online]. Available: https://en.wikipedia.org/wiki/Distance_ transform [6] (2003). [Online]. Available: http://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm [7] [Online]. Available: http://www.cs.utah.edu/~ssingla/IP/P4/Index.html [8] R. C. Veltkamp, “Shape matching: Similarity measures and algorithms,” Dept. Computing Science, Utrecht University, Tech. Rep. [9] [Online]. Available: https://developers.google.com/maps/documentation/javascript/ styling?hl=es-419 [10] [Online]. Available: https://mapstyle.withgoogle.com [11] [Online]. Available: https://console.developers.google.com [12] [Online]. Available: https://developers.google.com/maps/documentation/javascript/ get-api-key [13] (2015, December). [Online]. Available: http://stackoverflow.com/questions/ 34340578/installing-c-libraries-on-os-x [14] [Online]. Available: https://brew.sh [15] [Online]. Available: https://developer.android.com/studio/index.html?hl=es-419 [16] [Online]. Available: https://www.youtube.com/watch?v=nv4MEliij14&list= PL6v5F68v1ZZzTDq8VI9Jcmb0J99WRrYn4&index=6 31