Shop Forum More Submit  Join Login
The Red String of Fit by dekuNukem The Red String of Fit by dekuNukem
Another part of my project done! This is about smoothing the outline generated by the Canny Edge Detector by using cubic hermite interpolation on selected points on individual lines.

The result of Canny Edge Detector is impressive for picking out edges out of the original picture, however, the lines are not as smooth as you would expect, so I took serval steps to implement my edge smoother that irons out the sharp edges.

First, from the output of Canny Edge Detector, a BFS is attempted on each pixel that is the edge and not visited, the result is stored as edge trees, and the last point BFS visited is the furthest point from the start of BFS, this point is also stored as an end point for that tree.

Now, for each edge tree, another BFS is done from the endpoint mentioned above, the path between that endpoint and the last point visited in BFS this time is the longest path, which is recovered from an unordered map and stored as a line. Another unvisited point is picked from the this edge tree, a BFS is done to get an endpoint, and another BFS is done at that endpoint to get a path to be stored as a line. This process is repeated until all the points in that edge tree have been visited.

After all edge trees have been decomposed, there will be a collection of lines with one start point and one end point. For each line the first derivatives of X and Y component are calculated, since the graph is not continuous, they are approximated using central difference with 2 pixels offset each way. The first derivatives are then smoothed by averaging their values between each neighbor, then the second derivatives are calculated based on the first derivatives. Then interpolation points are chosen if the second derivative of a component is above a threshold, these points will be the ones cubic hermite interpolation work on.

And finally it's time for interpolation. Two modes are available, normal and crazy mode, normal mode is just a plain old smoothing while crazy mode messes everything up by multiplying an excessive coefficient on dt on each point. I used an external library to calculate the value, it's done on each component as t=x and t=y with t between 0 and 1, values and its first derivatives are fed in and results spat out, which actually is the easiest part. By doing this the path between interpolation points are replaced by a third-degree polynomial, which in turn is much smoother than the original graph. I updated the algorithm a little bit so now in crazy mode if the length of the new line is over 7 times longer than the original, that new line is recalculated with derivative coefficient multiplied 0.7 in each attempt until the new length in within limit. This ensures that every line is distorted but not unrecognizable.

You can see the difference in the pictures where I turned it up :)

I did came up with this algorithm all by myself.
No comments have been added yet.

Add a Comment:


Submitted on
January 19, 2013
Image Size
159 KB