Saturday, August 27, 2016

A new way to navigate countryside backroads and trails

One of my hobbies is scenic countryside trips on my mountain bike. I usually plan the route manually on Swedish map service eniro.se which have quite detailed maps, including really small roads and trails. The problem is the navigation. Eniro have a navigation application but you have little control over the route and the application sometimes routes poorly in walk mode, so I developed an alternative, and it works as follows.

You define the route by drawing three point polylines indicating your path through junctions. This can be done in Eniro maps, the option can be found in the ruler menu in the lower right corner. The waypoints need to be pretty accurate for good performance so this step is best done on a desktop/laptop. Should look something like this.



When you are done save all the polylines in a GeoJSON file, also in the ruler menu. The route is now done.

Next install my Android application which can be found here. In the application load the route and set off. When you reach a marked junction the application will issue navigation cues, either as speech, or vibration patterns if the media volume is zero. Uploading the route file to Google drive is a good way to make it accessible from your phone.

An example route around the lake Immeln can be found here. To view it just drop the file in Eniro maps. This route contains straight ahead cues and should therefore only be used with speech navigation. Vibration navigation only tells you left or right, not the actual bearing change, and is therefore not suitable for straight ahead cues.

One thing to keep in mind when opening existing routes by dropping them into Eniro maps is that you can't edit them due to a bug in Eniro maps where it will only save polylines drawn in the current session. So if you open a route, add a few polylines and do "download all" only the new polylines will be stored, not the ones originating from the opened file.

Other map services can also be used, so long as they support drawing polylines and saving them in GeoJSON.

Thursday, August 25, 2016

Figuring out my neighbors' schedules from leaking sound

All resources referenced in this post can be found here.

Unfortunately there is a fair amount of sound leakage between the apartments where I live. Mostly thuds originating from people closing doors, windows, cupboards, etc. If I stored metadata about every single thud in a database I could possibly get some interesting information from that data, such as my neighbors' schedules.

I decided to give this a try. For the recording I used a cheap stereo sound recorder (Olympus LS-12). To filter out the external sounds I had to write some code, process_recording.py. When sound passes through a wall or floor it is distorted, higher frequencies are dampened more than lower frequencies, so a lack of high frequency content is an indication that the sound may be external. The script works according to this principle, it looks at the frequency distribution and makes a decision on whether the sound originated from my neighbors or not. This worked pretty well in my environment, the false positive rate is close to 0% and the false negative rate is ~50%.

The "detect external sounds" algorithm ended up having 8 parameters that needed to be tuned. For the tuning I used a hill climbing approach. I constructed a tuning recording with 62 thuds and about an hour of environment sound. The tuning script randomly adjusted the parameters, processed the tuning recording, evaluated the result, and kept only the successful adjustments. This ran until I decided the tuning was good enough. A few days if I remember correctly. See tune.py for details.

Since I had a stereo sound recorder I thought it would be interesting to add sound angle to the metadata, to see if I could identify any sound source, so I did. The implementation uses phase correlation to get the delay between the channels and can be found in process_recording.py.

I couldn't find any tools suitable for analyzing the gathered data so I had to write some myself. The first one shows the number of thuds per hour over time, see sounds_per_hour.py for details.



As can be seen I did not chose the best time to gather data. First of all it was vacation times in Sweden, where I live, so people may be a bit less schedule bound than usually. Secondly there are some non-standard events in the period, a new neighbor moving in and repairs being done on the building.

My second analysis tool can select and show sounds according to a temporal pattern. The exact details on how it works are a bit difficult to explain but it can for example show you all weekdays combined into one diagram, or all Saturdays combined into one diagram. The implementation can be found in sound_viewer.py.

Lets start by looking at the angles for all sounds.



The banding is an expected result of the algorithm that calculates the sound angles so that can be disregarded.

A lot of action on the negative angles with a peak at -10 degrees. Unfortunately that does not point out any specific neighbor as both my neighboring apartments cover those angles.

Next lets look at how the thuds are distributed over time. Here are two diagrams showing how thuds are distributed over the day on Mondays to Fridays.


Someone gets up at 07:20 and something is happening at 11:30 and 17:00. Best times to relax are 21:00-00:00 and 02:00-10:00.

Lets look a bit closer at that 07:20 peak. Below are the angles for all the thuds that occur between 07:00-07:40 on Monday to Friday.

 


Only one neighboring apartment should be able to produce high positive angles so I'm pretty sure which apartment that is responsible for this peak.

Here are the weekend days.


The person that gets up at 07:20 sleeps in at the weekends, along with everyone else. Weekend daytime is a bit busier than during the weeks. Much of the 13:00 peak comes from a single event. I have a bit too little data for the weekend days so a single event can stand out in the diagram, but the general trends should be valid.

Tuesday, August 9, 2016

Detecting image manipulation in the noise

All resources referenced in this post can be found here.

If you assume that image noise is uniform over the entire image, and unique to a specific image sensor + setting (exposure time, sensitivity, etc), it should be possible to detect some forms of image manipulation by looking at the noise. If for example part of an image originates from a different capture it should have different noise characteristics than the rest of the image, and that could possibly be detected.

I wrote some code to see if this was doable, noise_lab.py. The application compares the noise at each pixel with normal noise to create an image depicting the deviation from normal noise. You can zoom along the "z axis" in the image to be able to see very small deviations. You can, for example, set a deviation of 0.2 to be black and a deviation of 0.21 to be white when showing the image.

The noise is captured by doing a FFT on a pixel's surroundings and dropping the DC component and the phase information. The normal noise is captured in the same way but from a user specified area of the image where all changes are caused by noise, for example the sky or a white wall.

When trying out my new application I quickly realized that my assumption that noise is uniform all over the image is not correct. I think there are a number of reasons for this but lets first focus on the relationship between pixel intensity and noise amplitude.



As can be seen there appears to be a relationship between intensity and noise amplitude. To be able to compare areas of the image with different intensity I need to normalize the noise amplitudes. I decided to model the relationship as a linear relationship where the slope is calculated from the user specified noise only areas. So now the user needs to input at least two noise only areas instead of only one which was the case before. The result looks as follows.



The linear model does not work well for low intensity pixels but it's good enough to see if this approach to detecting image manipulation has any future.

Below is an image composed of two different captures from the rear camera on my Nexus 6. The settings where 20ms ISO160 and 13ms ISO80. If everything works I should be able to see a difference in the noise. The image looks weird because I've tried to disable as much as possible of the camera's post processing to remove error sources. The image is what was read out from the sensor + bilinear interpolation + gamma encoding + jpeg encoding. What you get when running the following command on a dng file and jpeg encoding the result.

dcraw -r 1.0 1.0 1.0 1.0 -q 0 -M -o 0 -g 2.4 12.92 -j -W -H 1 image.dng



And this is what it looks like in the application.




It is quite easy to see the foreign part of the image but the low intensity parts of the original image appear to have the same noise characteristics as the foreign part, which is not ideal. This is a result of the noise normalization method's poor performance on low intensity areas. If you go back to the "Intensity - Normalized noise amplitude" diagram you will see that low intensity areas of image 1 have the same noise amplitude as normal intensity areas of image 2.

So that worked pretty well, but what happens if I feed the application with images that have gone through the camera's post processing? This image is also composed of two different captures from the rear camera of my Nexus 6. The settings where 33ms ISO241 and 17ms ISO134.






The "Intensity - Normalized noise amplitude" diagram is the most interesting one here. The noise variance has gone up (thicker y bands for each image) and the two images have moved closer to each other along the y axis. Both these things are bad if you want to detect image manipulation in the noise, and indeed the application is unable to detect the foreign part of the image. The completely black parts are due to saturated pixels (<= 0.0 or >= 1.0) being represented as zero difference.

If I make the noise difference between the two source images larger, 33ms ISO241 and 83ms ISO895, the application can detect the foreign part, but with such a big difference I can detect the foreign part just by looking at the image so the application does not add anything. This approach to detecting image manipulation is really only applicable to raw images with a few noise only areas. Unfortunately manipulated raw images are not that common, as far as I know anyhow, so this was a dead end.