Douwe Osinga's Blog: October 2016

Friday, October 21, 2016

WorldSizer

When I was 11 or so, I saw my first Times World Atlas. I was blown away. It was so much better in every way compared to the school atlas I was used to. The maps were huge, detailed and beautiful. The thematic maps and diagrams visualized everything from land use to economy to desertification.
Countries resized to reflect their populations

These days, with Google Maps and data visualizations of every type, you don't hear so much about atlases other than that people cut up old ones to sell the individual maps as wall decorations. There was one type of visualisation in the Times World Atlas that impressed me very much that I haven't seen online though: resized countries.

The idea is that you change the size of a country according to some statistic while trying to minimize the overall distortion of the map. As a kid, I wondered how you would calculate this - now I am pretty sure they just had an artist do their best. It is therefore with some pride that I am publishing an algorithm here to do something similar online: WorldSizer.

It's a two step process. The first, offline step takes the country data from the CIA Factbook and the shape information from Natural Earth. The CIA data is nice, because it is more evenly edited than, say, Wikipedia, but does need some massaging. Especially the country codes used by the CIA are seen nowhere else. One wonders if this has ever led to the wrong government being thrown over in a small Latin American country.

The shape files from Natural Earth have one or more shapes per country. The first step is to apply an area preserving projection to the shapes. Resizing a mercator map according to population would only cause confusion since it would still show India too small and Canada too big. The next step replace the points of the shapes with list of indexes into a global list of points. Here we also try to make sure that points on shared borders are only stored once. Since now points on borders are shared, we modify the shape of one country, it will also modify the shape of the other.

The online step takes the output of this and allows the user to pick a measure that the world will be "resized" to. For each country, we calculate the deflation or inflation factor needed to reflect the chosen measure. Then in an iterative process, we calculate for each shape how far the current area is off from the target area. If the shape is too small, all points of the shape are pushed away from the center, if the shape is too big, they are pushed towards the center.

For islands, this is enough. For countries that share borders, a tug of war process plays out. Especially in a region where all shapes need to grow or shrink, it takes a while for things to stabilize. Each shape also tries to maintain its original shape - for example, if you look at the map for population, you see India grow and sort of fall out of Asia as a blob before regaining its normal shape (only much bigger).

The shared borders and the country shape maintenance keep continents mostly in shape, too. But without extra care, islands will just drift into the mainland or each other. We stop this from happening by calculating "bridges". For each island, we look for a larger land mass nearby and anchor it to it. This keeps Ireland next to Great Britain, Great Britain next to France and Sri Lanka close to India.

Finally, we create some bridges by hand. Neither Spain nor Morocco are islands, but we'd still don't want them to crash into each other. Similarly, we attach Yemen to Somalia, Australia to New Zealand and Sweden to Denmark. In some situations this still leads to overlap. If you use proved oil reserves as a measure, the Middle East of course increases in size by a lot. But it has nowhere to go, so it pushes into the Mediterranean and squashes Syria into Greece.
More sad: scaled to number of people living with AIDS
One could add more bridges to force more map preservation, but this does come at a cost. The more forced the map, the less freedom the model has to preserve the shapes and get to the target sizes and it starts to behave more and more like a water balloon where you squeeze on one side and it just bulges out on the other.

As usual the source code is on GitHub. It should be fairly straight forward to use the worldsizer.js on another website with different data.

Wednesday, October 12, 2016

Styled Museums

The Prisma app became an overnight hit after it launched because of its great photo filters. Rather than just applying some face feature transformation or adjusting the colors, it rerenders a picture in the style of a famous artwork. The results are remarkable and quite recognizable. And it is no secret how this is done. The basic algorithm is described in a paper published a year ago called "A Neural Algorithm of Artistic Style"

Besides the scientific paper and the startup executing on it, there's also an open source implementation of the algorithm. I played around with it a bit and it also works well, although it seems roughly 100x slower than Prisma. It got me thinking, what happens if you use this to re-render pictures of museums in the style of their most famous work? That way you see what the building is like and at the same time what to expect when you go in.

Styled Museums does exactly that. It has the top 100 museums (by their wikipedia page view count) and their most popular works (same measure) and shows them on a world map. It uses the wiki_import frame work to get the data. You can click around and find your favorite museum and see what happens to it.


I think the fact that artistic style transfer is available as a scientific paper, a startup and an open source implementation is indicative of a wider trend. We now live in a world where we have three forms of innovation. The traditional scientific method where publicly financed institutions produce papers describing new ideas; the startup world that funnels large amounts of private money into ideas to see if they come to commercial fruition; and finally the open source world where individuals build something and share it with the world to build up their public profile.

These three engines of innovation aren't silos. Google started out as a scientific experiment, became a startup and a commercial success and now publishes scientific papers and open sources part of their technology. Github is a startup that is not only based on an open source project, but also hosts other open source projects. Twitter open sourced their data processing engine, which now helps academics keep up with what their peers in Silicon Valley are up to.

It doesn't always seem fair. The founders of Google became billionaires with technology developed while being employed by Stanford University, while the inventor of the world wide web works for a non profit. For years Werner Koch maintained the GnuPG email encryption package on the salary of a postman, while the founder of Hotmail is worth more than a 100 million dollars.

The 1980 Bayh-Dole Act in the US explains some of the difference between there and Europe. It allows universities and companies to claim patent rights on research undertaken with federal funding. On one level this doesn't seem right - if the government paid for research, shouldn't the patents end up with the government too? Then again, it turns out that the government isn't particularly good at doing interesting stuff with those patents - startups do much better.

And so we end up with Styled Museums. Inspired by Prisma, a VC funded company, I found the original paper which is based on research paid for mostly by the University of Tübingen, which in turn led me to an Open Source implementation. You can find the code used to get to Styled Museums (of interest is mostly the matching of museums and paintings) on Github, of course.

Wednesday, October 5, 2016

Introducing Karakame

This weeks project is a camera project: Karakame. Sorry, Android guys, iOS only. The app takes 5 pictures with 3 seconds in between. After adjusting for small movements of the camera, it will then for each pixel in the five images, pick the median one. This has the effect that when pointed at a scene where people walk in and out, it will remove those people in the aggregate picture.

It works reasonably well. The app is by all means no replacement for the main camera app, more a proof of concept. It seems like the sort of thing main stream camera apps should add - if you have an app like that you can get the source for this at https://github.com/DOsinga/Karakame. We were in Leipzig this weekend and I tried it out on a statue of Bach:
]
Bach in Leipzig

See? No people.

Karaoke famously means "Empty Orchestra" in Japanese - "hauntingly beautiful". Except for that it doesn't quite. Kara means empty (see also Karate - empty hand), but the "oke" bit is just the last bit of the English word orchestra. So I called the app Karakame, from the almost Japanese for "empty camera".

Some notes on the implementation. The app uses OpenCV which you can quite easily integrate into iOS these days. I extracted the interoperability code into a OpenCVBitmap class, so have a look if you're interested in that sort of thing. The image stabilization works really well. I normalize to the middle bitmap (i.e. the third one if you take five pictures). Image stabilization leads to the fact that some of the border pixels will be missing from some of the pictures, but by picking the median pixel value, most of the time we'll have values from other bitmaps.

I also experimented with object detection. OpenCV comes with a set of detectors called haar cascades that can detect faces, cars and people - no deep learning needed. It works well for face detection, but for cars and people I didn't get a lot of good results. The idea was to leave pixels inside rectangles that were classified as cars or people out of the median voting, but I took that out again.

Finally the median pixel implementation. Calculating medians in higher dimensions is expensive so I decided to just calculate the medians for the red, green and blue channels. This could lead to weird results, but in my testing it seemed ok. I suppose I could do a little better by calculating the median for the three colors and in the case where there is a disagreement, pick whatever pixel has the smallest distance to the other candidates.

If you have read this far, you're probably ready to get the project from github: https://github.com/DOsinga/Karakame