Google Blogoscoped

Monday, March 28, 2005

CHI Image Sorting

In CHI (the Collaborative Human Interpreter), you can sort anything, including images. Sorting usually breaks down to different algorithms which all have one thing in common: at a particular time they must compare two items to rank them. For example, given the number 20 and 15, the evaluation must rank 15 first. For images, we could compare different attributes, like beauty, size, or age.

As a sample CHI application, I want to sort 1,000 portraits by the age of the person portrayed. Using a single computer, this problem would take decades of AI to solve; using a human, this problem would take days to solve. We want to solve it without complex programming or letting a single human work for days. Again, CHI assumes that at any given time a large group of random people devote a little bit of their time to answer simple questions (technically, the interface CHI helpers access would best be implemented using Ajax/ XMLHTTP).

The age of the persons portrayed is not known so it must stay a guess. In CHI, this guess will be an approximation of a small group (of about 1 * 3 persons) or a large group (around 100 * 3). The small group in CHI is represented by the "person" type – it is basically one human, with some additional validation and fact-checking in the background (this is the multiplication by 3).

Besides the sorting algorithm, which shouldn't be the focus here, the image ranking program must repeatedly answer one question for each set of two images: "Who looks older?"

This question is asked in a multi-threaded, distributed way, so that the overall time to solve the problem (which includes answering a lot of questions by a lot of people) about equals the time to answer one question. We can assume it would take about three times as long to allow for certain delays. However, any single person who will answer too slow will be ignored, and a fallback answer by someone else faster is used (which means that any given time, more people are asked than answers are returned). This way, slower processes will not slow down the overall performance.

Given the 1,000 portraits as JPEGs, what is left to do?

First, a programmer must write a CHI program and manually hand it to the CC (Collaboration Controller). The programmer must have a registered developer key allowing only a restricted amount of daily usage; this restriction will still equal giant processing power, being a fraction of the global mind. This function is then registered as a web service (REST, parameterized URLs to get XML data back). The CC must parse the program and also handle the caching* of the portraits, ask the questions to the CHI helpers, and return an answer in proper XML.

*Caching is important to not stress the accessing server by the programmer, which is needed here – the CC server farm is immensely strong to handle controlling the large group of CHI helpers; the individual accessing server is weak.

Here's the sample CHI function:

function sortImageList(string urlImages)
    array arrImages = fileToArray(urlImages)
    collection string answers
    person anyone = find()

    // The following native sort function is performed
    // asynchronous, so that thousands of people will
    // compare different images at the same time

    answers = cc.asyncSort(arrImages, "sort_compareImages")

    return answers

// The following function was above passed to the
// native sort function "asyncSort" as specific
// comparison to base the ranking on

subfunction sort_compareImages(string urlImage1, string urlImage2)
    number older
    older = anyone.ask("Who looks older?", urlImage1, urlImage2)
    return older

The second server can be maintained by the same programmer, or a different programmer who merely utilizes an existing web service. This programmer may use PHP (or Python, Java/JSP, ASP/VBS, .NET, Perl, Lisp). He then wants to sort images by age of persons on them, and he simply passes a URL to the CHI web service. This URL is a CSV file (it could be another web service outputting the CSV); basically, just text-file with data, containing the 1,000 specific image URLs, separated by newlines:

And this is some pseudo-code representing the PHP, which would be needed to access the CHI:

function displaySortedImages()
    $urlWithImages = '';
    $urlCHI = '' .
            'developerkey=329818778JDEI2" .
            '&function=sortImageList' .
            '&images=' . $urlWithImages;
    $xmlResult = getXML($urlCHI);
    $xImages = $xmlResult->query('//data/answer');
    foreach ($xImages as $xImage)
        $sImage = $xImage->firstChild->data;
        $sImage = toAttribute($sImage);
        echo '<img src="' . $sImage . '" alt="" /><br />';
end function

In the end, we have a web page which had 1,000 random persons and now displays them sorted from youngest to oldest – based on a real-time approximation by the global brain.


Blog  |  Forum     more >> Archive | Feed | Google's blogs | About


This site unofficially covers Google™ and more with some rights reserved. Join our forum!