Breaking CAPTCHA in Python

Usually CAPTCHAs are analyzed by using neural network, it's a good approach, but it may be overcomplicated in simple cases. Presented below, much shorter algorithm can produce sufficient results for uncomplicated CAPTCHAs.

In this algorithm an image with unknown letter is compared with samples of known letters, the letter in the most similar sample is probably also the letter in analyzed image. It was implemented as a Python script, usage presented below:

bash-3.2$ python cracker.py test1.png 
e

bash-3.2$ python cracker.py test2.png 
p

It can't be directly used on a raw CAPTCHA, firstly small artifacts have to be removed from the CAPTCHA, secondly each letter should be stored in a separate image.

Read More

Edge Detection by using Genetic Algorithms

Abstract

In this post I will present an algorithm for searching edges in images by using genetic approach.

Algorithm

The image is preprocessed before its usage, firstly Gaussian blur is used to remove small artifacts that could pollute the result. I could be also done by using image downsizing and upsizing as I presented in the post about breaking captcha. Secondly the image is converted to black and white version to simplify the implementation.

Original image:

Edges found by using a genetic algorithm (100 generations):

In presented version each children has only one parent, so gene change is provided only by mutation. Each specimen has two genes: X and Y that describes a location on the image. If a specimen has a good set of genes (they point to a location near the edge), then he's healthy and strong so he can breed, but if his genes are weak, then he's weak too and soon he dies. The edge is defined by a fitness function as a point that has neighbor points with different color.

Strong species breed so after couple of generations theirs children will cover the whole edge. The final result is a set of genes (each is a point on the image) in the last generation.

Read More

Virtual Machine implemented as a Domain Specific Language in Ruby

Abstract

Some time ago I created a simple programming language that was compiled to its own assembly language, a file in this assembly language could be executed in a Virtual Machine or be compiled to an executable form. Today I will present an idea how to use Domain Specific Language (DSL) created in Ruby to load and execute the assembly file just as a regular Ruby script.

Implementation

A sample of an assembly file is presented below, it's intuitive except the "int" mnemonic, it means "interruption", int 0 pops element from the stack and prints it on STDOUT. There aren't any registers, everything is done by using a stack.

bar:
    int 0
ret

foo:
    call bar
    ret

main:
    push 13
    call foo
    ret

Read More

Motion estimation in super-resolution algorithms

Abstract

One of important steps in super resolution algorithms is the estimation of initial constants, without this the algorithms will produce useless higher resolution images.

From mathematical view, we may say that during taking a photo, the original scenery is gathered in high resolution, with some movement between each image (e.g. shaking hand or satellite moving on its orbit), next psf and the noise is added, at the end the image is downscaled.

To obtain higher resolution we need to somehow revert this process, to do that we need to estimate mentioned movements. In this post I will present two simple algorithms that I used to estimate the movement between images.

Read More