US Social Security Administration office http://www.ssa.gov/ created a service where you
can request the number of births of a babies per name per gender since 1880. However, their
pages are not easily accessible. After searching a while I found this page
http://www.infochimps.com/datasets/popular-baby-names-by-year-top-1000-us-social-security-administr
where is given a method of how to scrape SAS name list with a bash script.

!#/bin/sh
url=http://www.ssa.gov/cgi-bin/popularnames.cgi
mkdir -p names
for ((yr=1879 ; $yr <= 2010 ; yr++)) ; do
	echo $yr
	curl -d "year=$yr&top=1000&number=n" $url > names/$yr.html
done

Alternatively you can just download the data from infochimp’s website.

The problem is this is raw information and thus not very helpful. What we need is to have them in a data structure which will enable us to query the gender per name (ideally a distribution).

I used BeautifulSoup so as to parse the page and extract records.

import glob
from BeautifulSoup import BeautifulSoup

files = glob.glob('names/*.html')

for f in files :
	html_data = open( f ,'r').read()

	soup = BeautifulSoup(html_data)
	year = soup.find(id="yob")['value']
	tables = soup.findAll('table')
	trs = tables[2].findAll('tr')
	for tr in trs[1:-1]:
		tds = tr.findAll('td')
		print "%s,%s,%s,%s" % (tds[1].contents[0], tds[0].contents[0].replace(',',''), 'male', year)
		print "%s,%s,%s,%s" % (tds[3].contents[0], tds[2].contents[0].replace(',',''), 'female', year)

I stored the output to names.csv .

Then, to transform this information to a probability distribution per name I used the following code.

import json 

def prob( m, f ) :
    s = m + f
    return {'male':m/(1.0*s), 'female':f/(1.0*s)}

def load_data( file ) :
    names = {}
    f = open( file, 'r' )
    for l in f :
        d = l.rstrip().split(',')

        name = d[0]
        counter = d[1]
        gender = d[2]
        year = d[3]

        if name not in names :
            names[name] = { 'male':0, 'female':0 }

        if gender == 'male' :
            names[name]['male'] += int(counter)
        else :
            names[name]['female'] += int(counter)

    return names

db = load_data('names.csv')

names = {}
for d in db:
    p = prob( db[d]['male'], db[d]['female'])
    if p['male'] > p['female'] :
        gender = 'male'
    elif p['female'] > p['male'] :
        gender = 'female'
    else:
        gender = 'both'

    names[d] = gender

print json.dumps( names )

I saved this to names.json.

Finally, to query the gender of a name you just compare the probabilities

f = open('names.json','r')
names = json.loads( f.read() );
print names
def check_name( name ):
	if name in names :
                if names[name]['male']>names[name]['female']:
                         return 'male';
                elif names[name]['male']>names[name]['female']:
                         return 'female';
                else :
                         return 'unknown';
	else :
		return 'unknown'

The probability approach gives the flexibility to compute also a confidence of the gender for a given
name.

Then, the software part was to programm the robot to perform a taks, known as global localization. In simple words, imagine that you are given a map but you have no idea about the position of the robot in the map. Then, by using a ultrasound sensor you have to find the position and the using this information to drive the robot to a target. As you see, an error in the estimation can be disastrous.

The method we used for the localization part is know as Monte Carlo Localization. This method (uniformly) samples a number of hypotheses (particles) and then by comparing the measurements with the hypothetical measurements we re-sample hypotheses by weightening them so as the more consistent a measurement is, the more probabilities are that a hypothesis will be re-chosen.

After a serveral iterations of the MCL, an estimation of the position is found. Then, using this estimation, with the hope that it is also the correct position, we guide the robot to the target. So, how do we chose how to get from a position to another ? A simple and safe solution to that was to compute the Delauney triangulation of the map and then compute the dual graph of it, . Then we find the closest node of the dual graph to the robot and to the target. So, we have a starting position, a node (A) of that is close to the starting point, a node (B) of that is close to the target and a path from A to B on . Voila, this is the path that we have to follow so as to be as safe as possible that we won’t hit on a wall.

Well, here it is on action.

That was fun

Sol Robeson: Have you met Archimedes? The one with the black spots, you see? You remember Archimedes of Syracuse, eh? The king asks Archimedes to determine if a present he’s received is actually solid gold. Unsolved problem at the time. It tortures the great Greek mathematician for weeks – insomnia haunts him and he twists and turns in his bed for nights on end. Finally, his equally exhausted wife – she’s forced to share a bed with this genius – convinces him to take a bath to relax. While he’s entering the tub, Archimedes notices the bath water rise. Displacement, a way to determine volume, and that’s a way to determine density – weight over volume. And thus, Archimedes solves the problem. He screams “Eureka” and he is so overwhelmed he runs dripping naked through the streets to the king’s palace to report his discovery

Sol Robeson: Now, what is the moral of the story?

Maximillian Cohen: That a breakthrough will come.

Sol Robeson: Wrong! The point of the story is the wife. You listen to your wife, she will give you perspective, meaning. You need a break, you have to take a bath or you will get nowhere.

From Aronovsky’s Pi. I’ve forgotten how much I enjoyed that movie.

As the title suggests, my project is to research and develop a system which will make use of machine learning and music information retrieval so as to understand and then generate music automatically, simulating an improvising musician. In short, a system which will improvise in a jam session.

There are several ideas to begin with. The first milestone is to construct a system which will use simple midi input and fixed tempo, like the system suggested in [1]. However, the goal is to be able to use real instruments and beat to be extracted by rhythm instruments (take a look at [2] and [3] for real-time feature extraction).

Here is a list of the tools and languages i am planning to use:

• ChucK and weakinator.
• Pure Data and/or Max/MSP for interaction, programming, generation (using it with max for live).
• WEKA for machine learning.
• Ableton for audio synthesis (generative part)

Feel free to leave a comment, to make a suggestion or just tell me what you think.

References

1. Kitahara, Tetsuro, Naoyuki Totani, R. Tokuami, and H. Katayose. 2010. €œBayesianBand: Jam Session System Based on Mutual Prediction by User and System.€ Entertainment Computing €“ICEC 2009

2. Stark, A.M., and M.D. Plumbley. 2009. “Real-time chord recognition for live performance.”in Proceedings of International Computer Music Conference.

3. Stark, Adam M, Matthew E P Davies, and Mark D Plumbley. 2009. “REAL-TIME BEAT-SYNCHRONOUS ANALYSIS OF MUSICAL AUDIO Centre for Digital Music Queen Mary University of London London , United Kingdom.” Analysis 1-6.

In this example we are going to use the following images.

It’s easy to observe the followings. First of all, a fixed size (monospace) font has been used. This makes extracting all the letters and using them as masks to check each digit, one by one, very easy. Also, the alphabet is simple lowercase hexadecimal letters. Thus, we had to extract only 16 letters.

The first part was to to extract all the letters. To achieve that, first of all we sampled several images so as to be sure that the images we have contains all the 16 letters. Then, using a simple image editor we cropped all the letters, one by one. We had to be careful so all the letters be aligned properly. Here is the final mask.

As you can notice there is some noise which we have to remove. After playing with several techniques we finally ended to the following. We turned the image to greyscale. Then we used a threshold to remove some of the noise. Here is the example after the filtering (cropping also applied).

So, now we have the image almost cleared and some letters to play with.

Procedure

Move each letter across the image and take the difference of the pixels for each position and sum them. Thus for each position we have a score of how much the letter (mask) fits the letter behind it. Then, store for each letter the position where the maximum score found. Then sort by score, take the top five results (our captcha is five letters) and finally sort by position. The result is the CAPTCHA text.

More formally

Let

be the distance of the image , with the letter in position

Then

Thus, we need 5 letters with maximum  ordered by .

def p(img, letter):
		A = img.load()
		B = letter.load()
		mx = 1000000
		max_x = 0
		x = 0
		for x in xrange(img.size[0]-letter.size[0]):
			sum = 0
			for i in xrange(letter.size[0]):
			    for j in xrange(letter.size[1]):
					sum = sum + abs(A[x+i, j][0] - B[i, j][0])
			if sum < mx :
				mx = sum
				max_x = x
		return (mx, max_x)

Here is the code which implements this method. You can browse and download everything from https://github.com/ptigas/simple-CAPTCHA-solver

from PIL import Image

def ocr(im, threshold = 200, aplhabet = "0123456789abcdef"):
	img = Image.open(im)
	img = img.convert("RGB")
	box = (8, 8, 58, 18)
	img = img.crop(box)
	pixdata = img.load()

	letters = Image.open('letters.bmp')
	ledata = letters.load()

	# Clean the background noise, if color != black, then set to white.
	for y in xrange(img.size[1]):
	    for x in xrange(img.size[0]):
			if not(pixdata[x, y][0] > threshold \
			and pixdata[x, y][1] > threshold \
			and pixdata[x, y][2] > threshold):
				pixdata[x, y] = (0, 0, 0, 255)
			else:
				pixdata[x, y] = (255, 255, 255, 255)

	counter = 0;
	old_x = -1;

	letterlist = []

	for x in xrange(letters.size[0]):
		black = True
		for y in xrange(letters.size[1]):
			if ledata[x, y][0] <> 0 :
				black = False
				break
		if black :
			if True :
				box = (old_x+1, 0, x, 10)
				letter = letters.crop(box)
				t = p(img, letter);
				print counter, x, t
				letterlist.append((t[0],aplhabet[counter], t[1]))
			old_x = x
			counter = counter + 1

	box = (old_x+1, 0, 140, 10)
	letter = letters.crop(box)
	t = p(img, letter)
	letterlist.append((t[0],aplhabet[counter], t[1]))

	t = sorted(letterlist)
	t = t[0:5] # 5-letter captcha

	final = sorted(t, key=lambda x: x[2])
	answer = ""
	for l in final:
		answer = answer + l[1]
	return answer

print ocr('test.jpg')

[update]

Today I found this. Very nice tutorial for CAPTCHA solving using python and vector space searching.

The template currently used is the result of my work the last 2 days. It was developed from scratch using:

• 960 framework
• WordPress
• Adobe Photoshop
• CSS3 goodies and love

This is a first draft and it will get extended with several ideas i’m working on. Also, I plan to release it online. Check my github for updates.You can download it from http://github.com/ptigas/nullspace

Feel free to leave me any (constructive) feedback.

Cheers