Unlabeled Object Recognition in Google+

Google+ released an amazing feature that uses object recognition to tag photos. Here is a Reddit thread discussing it. Generalized object recognition is an incredibly difficult problem - this is the first product that I have seen which supports it. This isn't a gimmick - it can recognize objects in pictures without *any* corresponding text information (such as in the filename, title, comments, etc). Here are some examples on my photos (none of these photos contain any corresponding text data to help):


At first I thought this last one was a misclassification, until I zoomed in further and saw a tiny plane:


Of course, there are also many misclassifications since this is such a hard problem:

This squirrel came up for [cat]:

This train came up for [car]:

This goat came up for [dog]:

These fireworks came up for [flower]:

This millipede came up for [snake]:

PAQclass

I have released an open source classification algorithm called PAQclass: https://code.google.com/p/paqclass/. I originally created PAQclass when I was working on my master's thesis but I never got around to releasing it until now. PAQclass does classification via data compression. It uses one of the best compression programs available: PAQ8. Although it is very slow, I think PAQclass is probably close to state of the art for text categorization tasks.

Fathauer Fractal Tessellation

I have implemented a fractal in HTML5 canvas: http://www.byronknoll.com/kites.html. It is based on a fractal discovered by Robert Fathauer. Here is a zoomed-in view of the top of my fractal:



The fractal seems to have some interesting properties. Near the center of the zoomed-in image above you can see a "tunnel" of consecutively smaller triangles. There are an infinite number of these tunnels (and I think they exist in every direction). Along the vertical you can see there is pattern to the location of the tunnels. The distance between the tunnels is a geometric sequence with a common ratio of 1/3. As you travel into a tunnel, the hypotenuse length of consecutive triangles is also a geometric sequence with the same common ratio of 1/3.

O(n log n)

I have released a new version of my visibility polygon library. I improved the time complexity from O(n^2) to O(n log n) (where n is the number of vertices). O(n log n) is actually the *optimal* time complexity for this problem (since this problem can be reduced to sorting, and we know sorting is O(n log n)).

A high level description of the algorithm: First, sort all vertices according to their angle to the observer. Now iterate (angle sweep) through the sorted vertices. For each vertex imagine a ray projecting outwards from the observer towards that vertex - all we need to compute is the closest "active" line segment in order to construct the visibility polygon. The closest active line segment must be computed in O(log n) time (for each vertex). I used a special type of heap to accomplish this. The heap keeps track of all active line segments (arranged by distance to the observer). The closest line segment is at the root of the heap. Since line segments don't intersect (a constraint in the problem definition), the heap remains consistent. This property is essential - if the distance ordering between two line segments could change depending on the angle, then a heap would no longer work. So, we can find the closest segment in O(1) time and insert new segments in O(log n) time. The reason the heap I used is "special" is because it also allows removing line segments (when they are no longer active) in O(log n) time. Inactive line segments can't just be ignored and left in the heap - they need to be removed to maintain a consistent distance ordering. In a standard heap, removing an arbitrary element takes O(n) time (since it takes linear time just to find the element). My heap contains an additional map structure from element value to heap index, so elements can be found in O(1) time. Once an element is found, we swap in the last element in the tree and propagate it either up or down (which takes O(log n) time) to maintain heap correctness. Hooray!

Visibility Polygons

I have released an open source JavaScript library for computing visibility polygons: https://code.google.com/p/visibility-polygon-js/

Demo: http://www.byronknoll.com/visibility.html

I don't think there are any other JavaScript libraries which compute visibility polygons. A few years ago I released a Java game that used visibility polygons.