Posts

Another crack at the RX algorithm in Python

At the request of a commentor on a former post, I decided to write an updated Python implementation of the RX algorithm with NumPy (which actually out-performs my naive C implementation). You can download and install the module from GitHub.

At the heart of it all is the Mahalanobis distance metric,
\begin{align}d(\,\tilde{X},X_{i}\,)&=\sqrt{(\,X_{i}-\tilde{X}\,)^{\text{T}}\,\Omega\,(\,X_{i}-\tilde{X}\,)},\end{align}where \(X_{i}\) is some vector in the image's space (many times RGB), \(\tilde{X}\) is the average (or approximately average) vector along each channel, and \(\Omega=\Sigma^{-1}\) is the precision matrix.

I've found it's not really necessary to have the exact precision matrix in practice, so we may reduce the overhead of computing an average vector and covariance if the image is largely one color.  This computation can be neatly expressed with numpy.einsum.

Scaling an image to an appropriate number of pixels for your project

Image
Today I'm writing a Python module that works with image data (check back in a few days for my post about it) and I wanted to arrive at the optimal dimensions an image must be to have a certain number of pixels.

For example, if I want to see how fast my algorithm is for, say, 1 million RGB vectors, then I want to scale my example image to 1 megapixel.

In this post I'm working with an image that has dimensions \((3840,2160)\), or a size of about 8.3 million pixels. But what should the \(X\) and \(Y\) dimensions of my image be then, if I want it to be as close to 1 million pixels as possible?
First Attempt Let's write a Python function that preserves the aspect ratio of an image's dimensions and allows us to vary its size. from typing import Tuple def scale(X: int, Y: int, factor: float =1.0) -> Tuple[float, Tuple[float, float]]: """ Scale our image's dimensions by some factor, preserving aspect ratio. """ X_, Y_ = fa…

A few takeaways from PyCon, 2018

There were a lot of interesting talks this year, and although I didn't attend nearly as many talks as I would have liked, I got a lot out of those that I did.
Performance Python First and foremost has to be Jake Vanderplas' talk, Performance Python: Seven Strategies for Optimizing Your Numerical Code. My first takeaway from his talk is line_profiler, which is a command line tool that's intended to be used to profile your Python functions' execution time, line-by-line.

For example, let's use code from my last post and apply the convert function to a single image. We use line_profiler in the terminal by adding the @profile decorator to the function head (no imports necessary).
@profile def convert(im: np.array, transform: np.array) -> np.array: """ Convert an image array to another colorspace """ dimensions = len(im.shape) axes = im.shape[:dimensions-1] # Create a new array (respecting mutability) new_ = np.empty(…

Color space conversion

Image
I've been intrigued by Steven Pigeon's series on color spaces lately and wanted to give color space conversion a try in Python. In the following script I've reproduced several of the color spaces Pigeon mentions in the first five parts of the series.

Using NumPy this operation is almost trivial, but I added a few fun tidbits as well. Also note that, as I've mentioned before, PEP 465 has added the infix matrix multiplication operator @ to Python 3.5+.
#! /usr/bin/env python3.6 # -*- coding: utf-8 -*- # vim:fenc=utf-8 """ Convert colorspaces. """ from typing import List from tqdm import tqdm from functools import reduce from operator import mul import numpy as np import imageio import os ## Colorspaces Kodak_1 = np.array([[ 1, 1, 1], [-1, -1, 1], [ 1, -1, -1]]) Kodak_YCC = np.array([[ 0.299, 0.587, 0.114], [-0.299, -0.587, 0.886], [ 0.701, -0.58…

Fold a String into an Int type

While working my way through (Sullivan, Goerzen & Stewart, 2009), I came across the problem of converting a String to an Int using folds. This isn't that difficult a problem, but because I'm still a beginner to Haskell, I had to think about it for a few days.

Finally, I came up with the following (unsafe) solution using foldl.
import Data.Char (digitToInt) asInt :: String -> Int asInt [] = 0 asInt (x:xs) | x == '-' = (-1) * asInt xs | otherwise = sum $ foldl helper [] $ zip (reverse [0..(length (x:xs) - 1)]) (x:xs) where helper :: [Int] -> (Int,Char) -> [Int] helper totalList (order,digit) = digitToInt digit * 10 ^ order : totalList I separated the state of summing from the rest of the problem, using the fold to  'loop' over the list and raise each digit to the appropriate magnitude based on its position, just as one would in an imperative language. Thus, I believe this is a hybrid solution that uses both recursion and a f…

Binary Search in Haskell and Python 3.6

I've been learning a lot about Haskell lately, so I decided to write my own implementation of binary search after coming across Jacob Sheehy's implementation. In the following I wanted a nicer functional interface to locating a value in an entire list. I also wanted it to be safe, using the Maybe monad in the event a value doesn't exist or the list is empty.
-- A humble implementation of binary search in Haskell binarySearch :: Int -> [Int] -> Maybe Int binarySearch _ [] = Nothing binarySearch value list = search 0 ((length list) - 1) where search :: Int -> Int -> Maybe Int search i j sublist = do if i > j then Nothing else do let midPoint = ((i + j) `quot` 2) currentValue = list !! midPoint -- compare outputs one of LT, GT, EQ case compare value currentValue of LT -> search i (midPoint - 1) GT -> search (midPoint + 1) j EQ -> Just midPoint main :: IO() …

A string hash problem

Image
Earlier this week I was looking through various software developer jobs and I came across this one by Fog Creek. They've posted the following interesting problem, which is the subject of this post.
Find a 9 letter string of characters that contains only letters from acdegilmnoprstuw such that the `hash(the_string)` is 945924806726376 if `hash` is defined by the following pseudo-code: Int64 hash (String s) { Int64 h = 7 String letters = "acdegilmnoprstuw" for (Int32 i = 0; i < s.length; i++) { h = (h * 37 + letters.indexOf(s[i])) } return h } I had no clue what to do when I first read this. In fact, my first attempt was to brute force my way through \({16}^{9}\sim 68\cdot {10}^9\) possibilities. Obviously we need a better method than that.
from typing import Optional from itertools import product alphabet = 'acdegilmnoprstuw' def hash(string: str) -> int: "&quo…

Setting up ath10k

This post is meant as a simple reminder of how to get WIFI working in the event that I have to reinstall Debian on my Lenovo Flex 5, which appears to be a newer firmware.

First, run mkdir -p /lib/firmware/ath10k to create the subdirectory ath10k if it doesn't already exist. Now copy the QCA6174 directory from this GitHub repo there and rename the files QCA6174/hw*/firmware-5.bin* to just firmware*.bin.

Now reboot, and whoala! WIFI works.

Unfortunately, there still appears to be a few fails while loading the firmware, which I'll have to look into at some point. But for now, this is a quick fix to get things moving.
$ sudo dmesg | grep ath10k [ 2.186725] ath10k_pci 0000:03:00.0: pci irq msi oper_irq_mode 2 irq_mode 0 reset_mode 0 [ 2.463755] ath10k_pci 0000:03:00.0: firmware: failed to load ath10k/pre-cal-pci-0000:03:00.0.bin (-2) [ 2.463756] ath10k_pci 0000:03:00.0: Direct firmware load for ath10k/pre-cal-pci-0000:03:00.0.bin failed with error -2 [ 2.463765] ath10k_…

Tips and tricks I learned at PyCon 2017

This was my first PyCon, and it was a lot of fun! I wanted to write about my four favorite talks, and some 'tricks' I learned from them.

First is Decorators Unwrapped, by Katie Silverio. While I'm comfortable with decorators, I thought some of her silly 'useless' decorators were good examples. For instance, her no_op decorator, which is basically the identity.
from typing import Callable def no_op(func: Callable) -> Callable: # do nothing return func Another concept I hadn't really thought about was where *args and **kwargs come from in the following simple example, which calls the original function on some supplied arguments (it basically does the same thing as that above).
from typing import Any from functools import wraps def args_kwargs(func: Callable) -> Callable: @wraps(func) def new_function(*args, **kwargs) -> Any: res = func(*args, **kwargs) return res return new_function Note that *args and **kwargs a…

Matching stars between frames

Image
Lately I've been trying to find algorithms that will match stars between two consecutive CCD images. Needless to say, the task isn't at all easy, and my `naive' implementations have rather costly time complexities. However, with a little tuning, it's possible to get pretty decent results.

To begin, I installed Source Extractor (on Debian and Ubuntu, just type sudo apt-get install sextractor). Then I wrote this Python script to generate NN filters. As an example use, try running the following.
./psf.py --gaussian -i $(echo 3.1 > gaussian.conf && echo gaussian.conf) -s 6 -o gauss.conv && rm gaussian.conf && cat gauss.conv In the terminal you should see the following.
# Gaussian convolution filter for params 3.1 0.013196 0.019866 0.024375 0.024375 0.019866 0.013196 0.019866 0.029908 0.036695 0.036695 0.029908 0.019866 0.024375 0.036695 0.045023 0.045023 0.036695 0.024375 0.024375 0.036695 0.045023 0.045023 0.036695 0.024375 0.019866 0.029908 0.…