Sep 17

Repairing an Image in Python using Machine Learning (using KNN filters)

There are many great articles that can get you started on Machine Learning but so many of them focus on a handful examples that have little relevance to the real world. After all, there are only so many cases where one would need to determine the kind of iris based on it’s petals…

As such, one of the biggest challenges is not necessarily understanding Machine Learning – there are plenty good resources out there, but rather finding where to apply the knowledge.

While reading about KNN filtering it occurred to me that it would be a great candidate for repairing images with broken or missing pixels.

But first, what is KNN (or K Nearest Neighbors)? In short, KNN assumes that items with similar characteristics tend to bunch up, and tries to predict the value of an item based on the values of its closest neighbors. I will not go into too many details, because there are many great explanations on the net (one such article can be found here  https://www.analyticsvidhya.com/blog/2014/10/introduction-k-neighbours-algorithm-clustering/ ) I will focus, rather, on explaining the rationale behind image repairing.

So why did I think of images? Well, if we look at an image, we see that a lot of the pixels have similar colors to the pixels that are next to them. This is actually an observation that was used when creating  some older compression algorithms, anyone remember PCX files? So this means that even if we have a missing pixel, we can make a pretty good guess of its original color just by looking at the pixels that are around it.

I ran this algorithm on several images and got impressive results. For this example, I am using a random image that I got from here: https://pixabay.com/en/tree-sea-grass-nature-ocean-2435269/

Original image

What’s more, the code is not even too long, about half of it is just methods to handle the loading and saving of the image files.

Prerequisites (besides Python):

We’ll be using the following libraries:
  • Pillow for image processing (loading, converting and saving images)
  • numpy and pandas to work with data frames
  • pylab from Matplotlib for plotting graphs
  • scikit-learn for the actual KNN classification

The easiest way to install these is to use pip

pip install pandas numpy matplotlib sklearn Pillow
Ok, now that we have let’s get cracking.
The first step will be to load the image. We’ll be using the Pillow library to handle the image loading. If the image is not in the RGBA format, we convert it to RGBA.
def load_image(filename):
    im = Image.open(filename)
    if im.mode is not 'RGBA':
        return im.convert(mode='RGBA')
    return im

Once we have the image in the format that we need, we’ll map it to a dataframe, which, in our case represents a matrix that defines the image. Each pixel is defined by its X and Y coordinates and the color.

def convert_to_dataframe(image):
    pixels = image.load()
    data = []
    all_colors = []
    for x in range(0, image.width):
        for y in range (0, image.height):
            pixel_color = rgba_to_hex(pixels[image.width - x - 1, image.height - y - 1])
            data.append([x, y, pixel_color])
    return data, set(all_colors)

Because the Pillow image data defines each pixel as a tuple of 4 values for red, green, blue and alpha each, we will convert it to a single string representation of the format #RRGGBB. In this case I am ignoring the alpha value as I am not working with transparent images, but updating the code to include alpha would be trivial. As a note, the colors are being stored as strings, we would probably have a small performance boost if we stored them as 32bit integers instead. For the sake of simplicity, though, I chose not to do it.

def rgba_to_hex(rgba_tuple):
    assert type(rgba_tuple) == tuple and len(rgba_tuple) == 4
    return "#{:02x}{:02x}{:02x}".format(rgba_tuple[0], rgba_tuple[1], rgba_tuple[2])
If we’re here, let’s also write the functions to save the dataframe as image files. The save function receives one or more dataframes as parameter then combines the dataframes and writes them to a png file. It will become clearer why I chose to combine dataframes a little bit later on.
def save_to_file(filename, dataframes, size):
    ni = Image.new('RGBA', size, '#ff00ff')
    pixels = ni.load()
    for df in dataframes:
        for row in df.itertuples():
            pixels[size[0] - 1 - row.x, size[1] - 1 - row.y] = hex_to_rgba(row.color)
def hex_to_rgba(hex_string):
    return int(hex_string[1:3], 16), int(hex_string[3:5], 16), int(hex_string[5:7], 16), 255

Ok, so far we have the image, we can load it and extract the data in the format that we want, let’s do that:

def run(image_name):
    im = load_image(image_name)
    filename, file_extension = os.path.splitext(image_name)
    data, all_cols = convert_to_dataframe(im)
    df = pd.DataFrame(data, columns=['x', 'y', 'color'])

Now, let’s simulate that our image is damaged. We’ll do this by randomly removing 30% of the pixels in the image. The simplest way to do this is to take advantage of the methods numpy already gives us. np.random.uniform(min, max, length) creates a list of values between min and max. If the value is greater than 0.7, we make it True, otherwise False. Then we only keep the pixels from the original dataframe for which this value is False. This will keep roughly 70% of the original pixels.

is_missing = np.random.uniform(0, 1, len(df)) > 0.7
train = df[is_missing==False]

In order to actually see the result, I am filling in the missing pixels with magenta. This is an optional step, just so that we can see what the “broken” image looks like. Let’s save the image to a file so we see what the “corrupt” image looks like.

save_to_file('{}_missing{}'.format(filename, file_extension), [train], (im.width, im.height))

Image missing pixels

How do we choose the value of K?

So now to the big question. We know that KNN looks at the K closest neighbours to determine the value of the current pixel. But how do we pick this value? Well, that’s simple… Let’s take the data we have, and split it into two sets. The first one will be the training set, the second one will be the test set. We’ll use 80% of the data as a training set and 20% as a test set. Then, we’ll try to predict the values for the 20% and compare them against the original values for a range of values for K ( I chose between 1 and 20). We’ll then compare the accuracy and take the value of K that gives us the best accuracy.

def plot_k(data):
    accuracy = get_accuracy(data)
    results = pd.DataFrame(accuracy, columns=["n", "accuracy"])
    pl.plot(results.n, results.accuracy)
    pl.title("Accuracy for variable K")
def get_accuracy(data):
    accuracy = []
    print "Plotting K..."
    is_missing = np.random.uniform(0, 1, len(data)) > 0.8
    train = data[is_missing == False]
    test = data[is_missing == True]
    for n in range(1, 20, 1):
        clf = KNeighborsClassifier(n_neighbors=n)
        clf.fit(train[['x', 'y']], train['color'])
        preds = clf.predict(test[['x', 'y']])
        k_accuracy = np.where(preds==test['color'], 1, 0).sum() / float(len(test))
        print "Neighbors: %d, Accuracy: %3f" % (n, k_accuracy)
        accuracy.append([n, k_accuracy])
    return accuracy

Plotting the K variable

We can see from here that we get the best results when K is 3 (actually, 3,5,7 are very close, we could pick anyone of those). However, after K=7 we see a decrease in accuracy. That’s most likely because the algorithm is overfitting (i.e. looking at noise in the image and thinking it’s actually a part of the image).

Note 1: I was using an image with a limited number of colors (256). When using a larger palette, the accuracy can get much lower (in the 30s) but the results will still be looking good.

Note 2: Computing the accuracy of K can take a long time for images with lots of colors. For instance, computing the accuracy for a 1280×915 and 32bpp image took 5 hours on my Macbook Pro.

Alright, now that we have the K value, we can actually create the classifier and train it.

    clf = KNeighborsClassifier(n_neighbors=3)
    clf.fit(train[['x', 'y']], train['color'])

Classifier up and running… let’s predict!

    preds = clf.predict(test[['x', 'y']])
    test.color = preds

And now that we have the prediction, let’s combine the prediction with the original data and voila! We have a complete image… We lost a little bit of the details, when comparing it to the original, but if you didn’t put them side by side it would be hard to spot.

Image with missing pixels restored

I am sure there are ways to improve this, but the results are more than satisfactory.

The full code can be found here: https://gist.github.com/radulucaciu/df0b30453338946e639449710862822d

Sep 13

Apple’s sense of humor

I had a good laugh today when I got a nice error from XCode.

I made a mistake and passed the wrong variable to NSMutableArray::initWithCapacity.The value of the variable was -1 which, obviously, got cast to an unsigned and caused a crash. But I found the error message funny.

Terminating app due to uncaught exception ‘NSInvalidArgumentException’, reason: ‘*** -[__NSPlaceholderArray initWithCapacity:]: capacity (4294967295) is ridiculous’

Thanks XCode team, you made my day brighter!

Jun 13

When Google strikes… Google API client library for Objective C linking errors

Yesterday I decided to play around with Google Analytics and get familiar with their API. I wanted to create an iPhone app that loads data from Google Analytics and draws graphs for some of the metrics I considered important. But mainly this was to be just a learning project.

I looked around to see if there’s anything out there to handle all the server communication since it’s based on OAuth2 and I didn’t want to implement everything from the ground up and I found this: Google APIs Client Library for Objective-C

Aside from the documentation being sparse, at best, there was no example for the Analytics part either. I’ve copied the Analytics files and the required dependencies into my project everything seemed to go smooth… except that it didn’t.

When trying to compile I’d get a nice linker error saying that there are 97  duplicate symbols (see below). Now, debugging linker errors is about as much fun as trying to count grains of sand while wearing boxing gloves. I checked that the .m files are not included twice under Build Phases -> Compile Sources. Nope, all seemed ok. I even removed the files and added them manually…. No luck. I cleaned and rebuilt… Still nothing. Talk about finding the needle in the hay stack… I ended up looking through the source code and I rested my eyes on this little gem called GTLAnalytics_Sources.m

#import "GTLAnalyticsConstants.m"

#import "GTLAnalyticsAccount.m"
#import "GTLAnalyticsAccounts.m"
#import "GTLAnalyticsCustomDataSource.m"
#import "GTLAnalyticsCustomDataSources.m"
#import "GTLAnalyticsDailyUpload.m"
#import "GTLAnalyticsDailyUploadAppend.m"
#import "GTLAnalyticsDailyUploads.m"
#import "GTLAnalyticsExperiment.m"
#import "GTLAnalyticsExperiments.m"
#import "GTLAnalyticsGaData.m"
#import "GTLAnalyticsGoal.m"
#import "GTLAnalyticsGoals.m"
#import "GTLAnalyticsMcfData.m"
#import "GTLAnalyticsProfile.m"
#import "GTLAnalyticsProfiles.m"
#import "GTLAnalyticsSegment.m"
#import "GTLAnalyticsSegments.m"
#import "GTLAnalyticsWebproperties.m"
#import "GTLAnalyticsWebproperty.m"

#import "GTLQueryAnalytics.m"
#import "GTLServiceAnalytics.m"


Arghhhhhhhhhh! Importing .m files? Whyyyyyy? I simply left out the file and all works without a hitch. But I did waste one hour to track this down.

Continue reading →

Nov 11

Upgrading to iOS5 causes ‘No Provisioned iOS devices are available’ error

I finally decided to upgrade my iPhone to iOS 5 today. The upgrade process was pretty smooth, but once it was done, I was no longer able to run the apps from XCode. I kept getting the no provisioned ios devices are available with a compatible ios version error.

Turned out that all I had to do was to go to Window->Organizer and, from the Devices pane, select my iPhone and click on Use this phone for development.

Easy solution, but was not immediately obvious to me

Sep 11

Apple pains – Invalid signing certificate

I’ve been trying for the past two days to submit a new version of CashBase but I kept getting the dreaded “application failed codesign verification. the signature was invalid, or it was not signed with an apple submission certificate. (-19011) ” error. (Note: after migrating to XCode 4, all sorts of weird things happen, talk about a buggy piece of software, right there)

I tried all the tricks in the book: revoke the distribution certificate and re-create it, clean, made sure that the Code Signing for distribution is the correct one, etc. Nothing!

After many failed trials, I thought of taking a look at the entitlements used to sign the binary:

codesign -dvvv CashBase.app

I noticed that the Authority key was using my iPhone Development certificate. Turns out that the Archive Scheme in XCode 4 decided to switch all by itself to the Release Build configuration instead of the Distribution. Changing it back to Distribution solved my problem

With hindsight, I should have noticed that the binary was being compiled to the Release-iphoneos instead of the Distribution-iphoneos folder.

Note: A collection of helpful hints for this error can be found here

Edit: To edit the scheme, go to Product -> Edit Scheme. Select the Archive Scheme and make sure that the Build Configuration is set to Distribution (this is for XCode 4.x)

Feb 11

Windows 7 – keyboard hooks stop working, a workaround

It seems that sometimes applications that install a keyboard hook (to monitor media keys, for instance) can randomly stop receiving the keyboard commands. I’ve seen this problem happen with the Groovie app. I’ve also heard of it happening with various music and video players.

It turns out to be a bug in Windows7; under full-load, the Operating System will not allow sufficient time for the hooks to process the messages and will remove them without notifying the application.

One workaround that I found was to increase the Hooks Timeout setting in the Windows registry:

Go to HKEY_CURRENT_USER\Control Panel\Desktop and set the LowLevelHooksTimeout to a larger value, I used 2710 (which is 10 seconds)

Hope this helps someone.

Feb 11

Grooveshark keyboard hook

The guys at Grooveshark did an awesome job switching from the Flash based player to Javascript (as a side note, I just wish they’d lose the Flash ads, they make my Macbook Pro’s CPU hit 70% load just listening to music).

This allowed me to write a new application that captures the play/pause/forward/backward media keys and send the necessary messages to the player. Using the app is so much simpler as well, just launch the app and you’re ready to go! No need to go through the tedious process of selecting the window and keys, everything should be straightforward.



Since Grooveshark never replied to my email, I’m publishing the code

Groovie Source

Feb 11

iPhone autocomplete class

While working on the Cashbase iPhone project ( CashbaseHq ), I found myself longing for an autocomplete feature, but could not find anything on the web. So I decided to build my own. The functionality is identical to the way autocomplete is used on the web. Upon typing a text in the text field, a list with suggestions appears bellow it. Selecting an item from the suggestions list will hide the list and add the word in the textfield.

This is how it looks in our app (for space reasons we have designed the suggestion list to be displayed above the field that requires autocomplete, but you can easily display it below – just see the demo app)

How to use:

Import the Autocomplete.h file

#import "Autocomplete.h"

Prepare the target UITextField for autocomplete by disabling the iPhone’s default autocomplete feature. You usually do this in the viewDidLoad method.

//disable the iPhone's default autocomplete feature
textField.autocorrectionType = UITextAutocorrectionTypeNo;
//create the Autocomplete class and initialize it with some data
autocomplete = [[Autocomplete alloc] initWithArray:[[NSArray alloc] initWithObjects:@"apples", @"oranges", @"bananas", @"peaches", @"grapes", @"blackberries", @"strawberies", @"watermelons", @"mangos", @"pears", @"lemons", nil]];

Now, when the text in the text field has changed (ie: in the EditingChanged handler), just call the GetSuggestions method, which will return an array of strings that match the parameter passed

NSArray *suggestions = [autocomplete GetSuggestions:textField.text];

You can do whatever you want with these suggestions, I displayed them in  a table view and when the user taps a cell, the text is added to the text field (see attached demo project)

Autocomplete Demo Application

Autocomplete Source

Nov 10

Simple Grooveshark play / previous / next media keys hook

Notice: This software is obsolete, please read this post instead

A few days ago, a good friend of mine told me he’d like to be able to play/go back/skip the songs on Grooveshark, and asked whether I could write a small application to implement the functionality he needed.

I thought this to be a great occasion to stick my nose in C# and see what’s what. A few hours later I had a simple application that does just what was required. There’s nothing fancy about it, and I don’t plan on adding any new features, but feel free to grab the source code and modify it after your own heart’s desire.

How to use:

  1. Open the Skipper app
  2. Open Grooveshark in your browser – I hope you’re using Firefox or Chrome! If you’re using Internet Explorer, help make the world a better place and download one of the browsers mentioned above!
  3. Drag the Window Finder tool on top of the Grooveshark window
  4. Add the X,Y coordinates for the play / previous / next buttons in the app (you can find these by taking a capture of your screen and using any image editing software to find the coordinates). Please note that the coordinates have to be in Window space, meaning that you should compute X and Y starting with from the top-left corner of your window, not from the top-left of your screen)
  5. Make sure you don’t change the tab in the browser. The Grooveshark tab must ALWAYS be active. If you need multiple tabs, I suggest you open Grooveshark in a separate browser.
  6. Use the media keys (play / previous / next) on your keyboard to navigate through the songs.
  7. NOTE: the browser window does not have to be active, it can be hidden by other windows and this will still work

I’ve only tested this on Windows 7 but it should work in Vista / XP as well.

If you need additional functionality, feel free to modify the source code, I will not have time to upgrade it.

Edit: A big thank you to Ruurd Moelker for taking the time to improve the application by adding the following:

  • Media button target selection with mouse cursor.
  • Always visible target pointers
  • An icon.
  • Trayicon support.

Download Skipper

Download Skipper Source code

Nov 07

Yahoo! Messenger archive search

For quite a while now I’ve been frustrated by the fact the Yahoo! Messenger does not give you the option to search through the archive. I’ve found myself wishing for that search function more and more often lately. Having to browse through each conversation, to find what I needed, was inhuman – especially since I didn’t remember when the conversation took place!

So I decided to build a small application, that reads the Yahoo! Messenger Archive and implements basic keyword search. The first version of the software is already complete and can be downloaded here. The current version is completely functional, though many improvements are still in store.

So far I’ve only been interested in functionality, so the interface is kind of awkward, but will be one of the last things I will take care of. There are still some issues with the multithreaded code that have to be sorted out, but I’ve found this utility helpful a few times already.

Check it out and let me know if you find any bugs or have any suggestions!