Discretizing 2D Images Into Polygonal and Point ModelsSimplifying complex images into a simple data formatTim ChinBlockedUnblockFollowFollowingApr 21The real world is all curvy and complicated.
With burgeoning robotic technology and autonomous vehicles there is a common need to simplify objects in more manageable forms.
Additionally, our world is continuous (for the most part), yet our technology interprets content digitally.
So, for any world interaction there will be some level of discretization.
For a robotic grasping project I am developing, I recently ran into this problem.
A 2D shape exists and surface information needs to be extrapolated in order to determine where to grab the shape.
Luckily, OpenCV has methods of simplifying curvy contours into more polygonal looking shapes.
Let us look into these functions and their results.
A key and the result after salience detection.
After being given an image we grab the item of interest using our favorite salience method.
As in the example above, this creates a fairly decent mask of the object of interest.
It can be seen that difficulties will arise if any sort of geometric manipulation is attempted.
The curvature of the key’s handle will make it to difficult to determine a normal vector, for example.
Additionally, noise picked up during segmentation will create erroneous edges.
The convenient OpenCV function approxPolyDP() is used to approximate a contour into fewer points.
The function uses the Ramer–Douglas–Peucker algorithm to reduce the number of points.
This is a recursive algorithm that takes a constant value, ε.
The algorithm begins by finding the farthest point from two starting points.
If the point is less than ε, then all the points between the first two starting points are discarded.
Otherwise, the algorithm bisects the set of points again and recurses down to the next set of points.
The process is repeated with each bisected set.
A handy animation of the Douglas–Peucker algorithm.
SourceBy varying the value of ε, different levels of “discretization” can be achieved.
The greater the value, the more polygonal the final shape will be.
From Left to Right, Top to Bottom: ε = 0.
5, 2, 5, 20For many applications the above is a perfectly fine solution.
However, some algorithms that deal with discrete real world objects will further break up polygons into consecutive points.
This will involve more information to store, but can be more informative.
Creating a point based frame of an object is not too difficult from the above polygons.
Having an array of consecutive vertices that make up the polygon, we can iterate along each edge.
For each edge, a vector is determined between the two vertices.
Along each vector, a percentage of points are generated depending of a desired resolution.
The resolution we use will determine the number of points made on each edge.
The dotted with a resolution of 10%With the described method, fairly complicated shapes can be simplified to simple edges or dots.
This is useful if any interaction needs to be performed with an object or geometric analysis needs to be performed.
If a certain object recognition scheme is being built, it can make more sense to compare simplified objects.
This allows us to ignore details and idiosyncratic features.
This article is part of an ongoing project.
The work-in-progress C++ code can be found on my github:TimChinenov/GraspPictureCode for segmenting salient colored images and determining a grasp.