Calculating the number of repeating objects in an image

Recently I was asked to help solve a problem determining the number of seats in an airline. An example of such an airline layout is shown below (click to view the bigger image.)



I decided to use the method I knew best, Cross Correlation. The idea is to cross correlate the template of the seat (i.e., an image of a single seat) with every pixel in the airline layout image. The template (coordinate origin is its center) is moved over to a particular pixel in the image. The cross correlation coefficient is calculated and the value is used as the intensity of a new image. This is repeated by moving the template to every pixel in the airline layout image. The pixels for which the template matches perfectly with the airline layout image, will have the correlation coefficient close to 1.


Above: A hard to see template of the seat.

The results of the cross correlation is shown below (click to view the bigger image.)

The bright spots in this image are the points with the highest correlation. It then becomes a simple process of segmenting the high intensity pixel.

To perform these operations, my natural choice was Matlab and its Image processing toolbox.

im = imread('airline_seating.jpg');
im = rgb2gray(im);

im_template = imread('template.jpg');
im_template= rgb2gray(im_template);

C = normxcorr2(im_template, im);
C1 = C>0.7;

stat = regionprops(C1);
noofseats = size(stat,1);
disp(['Number of seats = ',num2str(noofseats)]);


In the first 4 lines of code, we read the airline layout image and the template image. To obtain the correlation image, I did not have to write my own correlation function instead Matlab has one already ready to be used. This function, normxcorr2 needs the airline layout and the template matrix. Once the correlation image is obtained, we segment it based on the logic that any pixel with value more than 0.7 is considered as pixels corresponding to the center of seat. Since the center of the seat did not segment as a single pixel, I could not count the number of pixels as the number of seats. Instead I calculated the number of regions using regionprops and store it as a structure. The number of elements of the structure is the number of seats.

Spamming of HTML forms - one case

Recently I found that a newspaper in its online edition switched from image based CAPTCHA system to solving a mathematical puzzle, in-order to prevent spamming of their comment section using a computer program. A screen capture of the same can be found below.



The problem with such a system is that they can be easily solved using a computer, which defeats the purpose of using it to differentiate human and computers apart. To test my own skill, I wanted to write a program that can download the page, read it and solve the puzzle as well. Using the information I obtain, I could then post comments without human intervention.

To accomplish this task, I used the usual suspects like python and and the HTML parser, BeautifulSoup. BeautifulSoup reads a string of html or xml and converts it to a tree. Using the tree, it is easy to navigate through the tags or search for a particular one based on id or name. It is also powerful enough to differentiate tags based on CSS class in html tags.


1. import urllib
2. from BeautifulSoup import BeautifulSoup
3. import string,re

4. doc = urllib.urlopen('http://www.somesight.com/comment/reply/1854565').read()
5. soup = BeautifulSoup(''.join(doc))

6. a = soup.findAll("span",{"class":"field-prefix"})
7. b = a[0].contents[0].split("=")[0].split("+")
8. c = [int(bs) for bs in b]
9. captcha_response = sum(c)
10. print a,captcha_response

11. token1 = soup.findAll("input",id="edit-captcha-token")
12. token1_val = token1[0]['value']
13. print token1,token1_val


The two important information that I need to calculate are the captcha_response which is the solution to the mathematical problem and the captcha_token, a hidden html field in the webpage. Line #6 searches for a class, field-prefix in span tag. This tag contains the string for the mathematical puzzle that needs to be solved. I obtain the contents of this string and split it in-order to obtain the individual numbers in a list. Finally I convert those numbers from string to integer in Line #8 and sum them using line #9.

Line #11 searches the hidden captcha token, stored in the input tag with id="edit-captcha-token".

Armed with these two information, we can post any name and comment to the form. The comments were moderated but it would still require lot of human intervention to clear the spams.

I informed the webmaster of this issue. They have since moved to a image based system. I removed all reference to the site in this blog post and program in-order to keep their anonymity.

Ajax in django

Asynchronous Javascript and XML (Ajax) has become the most important tool for web developers in improving the look and feel of their website. A normal HTML request is sent by a client with request for a particular page. The server prepares the page and sends it to the client browser that renders the page. This approach is still valid for most pages. But the problem is that the whole page gets rendered every time the server processes a request. This might be acceptable for some websites but sites like google maps, stock ticker sites would rather modify a small portion of the page rather than reload them completely. Ajax plays an important role in such applications.

Django provides support for Ajax and my google-fu turned up a few of them that were really good. The problem I had with them was that the sites focused more on how syntactically Ajax can be executed in Django rather than the overall principle. So, in this post I will focus just on the basic principles of Ajax in Django. The anatomy of a typical django request can be summarized by the image below. The request comes in from the client, the view function processes it and the response is returned using a call to HttpResponse or render_to_response etc.



In a normal django request, the response is in the form of HTML or CSV or some such file. Ajax needs JSON or XML instead. Hence django is almost ready for Ajax. The only extra step is the need to serialize the data in to JSON or XML format. Django makes it easy by providing serializers that are builtin.

During the process of serializing, django takes two approaches. The first approach is for serializing list of django model objects and the second approach is for everything else. The everything else could include any dictionary of values that you create but need to pass through serialization. Lets look at each approach separately. Both approach are serialized using simplejson built in to django. In the former, django provides a separate module and hence you do not have to make an explicit simplejson call. In the latter, you need to make explicit calls to simplejson functions.

In the first approach, we pass the list of django model objects to the serialize function in the serializers module.

 from django.core import serializers
 
 def search(request, query):
  return serializers.serialize("xml",User.objects.filter(lastname__startswith=query))

In the second approach, we need to make a explicit call to simplejson. In the program below, we first load the simplejson module. We then create our dictionary using the values, number and image_loc. We then return the json value using simplejson.dumps() function and django's HttpResponse function. The javascript on the django template will then modify the HTML page according to the values in the json object. If you use the first approach to the dictionary that you created, it will give an error, "'str' object has no attribute '_meta'"

from django.utils import simplejson

def servevalues(request):
    number = 10000
    image_loc = 'http://www.google.com/images/logos/ps_logo2.png'
    data = {"number":number,"image_loc":image_loc}
    return HttpResponse(simplejson.dumps(data),mimetype='application/javascript')

Remember:
1. Ajax calls to django are very similar to http request calls. Both return some form of textual information. Hence syntactically they look alike

2. There are 2 approach to serializing. The first approach is for django model objects and the second approach is for any other object / dictionary that you create. In either case, the code that you have to write is minimal and simple, the django way!

Keep tab on items you lent using borrow-err.com

On my free time, I have been working on a small but useful and interesting project. It resulted in the site http://www.borrow-err.com/

The reason for creating the site was my forgetfulness. I lend books to others and I forget about it. So, I decided to create a website where I can keep track of items I lent to others. If you would like to try it, just key in the details of the items and the name of the borrower in to the home page. The website will then send you a reminder email every month for the items you lent. If you are lucky and you get your items back, you can remove them from the list using the links provided in the email.

You can access it using any browser. The page is also light enough that it loads fine in mobile browsers as well. So whether you are at home, office or on road, you can use borrow-err.com to keep track of items that you lent. Try it and give me your feedback.

Remember: borrower's err, so you need borrow-err.com

October 5th, 2010: The previous version had the bare minimum styling. Hence I made some changes and I believe the new version is more pleasing to your eye.