Edgestract - An 'uncanny' edge detection algorithm

A project log for Roboartist

"Can a robot turn a... canvas into a beautiful masterpiece?" - Will Smith (I, Robot)

Wow! There has been quite a lot of buzz about the Roboartist, last week and we even got to the pages of Hackaday.com, Engadget and Popular Mechanics. We're delighted and thankful for all the attention we're receiving. Let's just clear this one little thing that seems to be floating: We're not using the Canny Edge detection. We were for a while. However things got messy pretty quick. Read on to find out what went wrong and how we beat it. It was a classic case of necessity spawning a solution.

The output of Canny filter gives emphasis to the individual gradient around each pixel separately in determining if the pixel should be an edge or not. However, it does not include the length of a structure formed from a group of adjacent pixels, so structures the length of only a few pixels show up as edges. This is not really good news for Roboartist because it means he'll be spending a lot of time poking on the drawing sheet ; messing up the good renderings and annoyingly taking up a lot of time on that ( yup, happened ).

We are clearly better off with an algorithm that evaluates the length of each structure and then along with the sum of the gradients at each pixel determines whether the structure as a whole is classified as an edge or not. And that's exactly what we built. Edgestract.

Ok, so how do we find out the length of each structure for this? We correct all forks and branches in all the individual structures until only perfectly open structures or perfectly closed structures remain.

In the above stage, all branches and nodes are removed and only selected open and closed structures remain. We've also marked all the endpoints on all open structures as shown. We're now good to perform structure the tracing process!

First open structures are evaluated: we start from one end of an open structure and we move to the next adjacent pixels one by one and increment length variable by 1 for each pixel transversed. When we reach the other end point we get the total length of that structure. We then search and jump over to the end point of the closest surrounding open structure. To prevent the same structures from being infinitely traced by this process we delete each pixel information as we trace along it.

Ultimately we get the lengths of each open structure and all of them are deleted. The information regarding the path we traced and the length of each open structure is stored. We then repeat this process for closed structures, starting from any point on a loop structure (since loops don't have end points) and after covering a complete loop, jump to the nearest point of another closed structure. All the length and path information is combined with the earlier data. We can now select edges from the individual structures knowing the length of the structure from the tracing process and  combining that information with the path taken by it. The path gives info about all pixels covered by that structure, hence the sum of gradients of all pixels obtained.

Check out the following image.

We've superimposed the edge results onto the main image. You'll find all the tiny structures get rejected as their lengths are too small. This could easily backfire, but by carefully controlling a few parameters, you can reduce the noise involved. Hence image appears neater and duration for drawing is reduced. Edgestract is optimised to churn out 'drawable' images. Through the tests we've put it through, it was found that it gave us significantly lesser headaches.

Edgestract : saving the world before drawing time :)