The project specifics limited the output designs to a single color with a constant stroke weight and a maximum size delimited by the wall to paint. Due to the limited accuracy/resolution of the drones, the battery capacity and the cost of flight time, the software design focused on extracting the relevant information from the images and minimizing the drawing time, maintaining a faithful abstraction to the original image.
First of all, we need to decide how are those digital images going to be physically interpreted and painted by the drones.
Halftone and Stippling techniques are based on the constitution of sets and patterns that, through repetition, create textures and silhouettes. A low resolution stippling would result into a non defined shape.
During the first steps of the research process, it became clear that abstraction was key to to represent the essential parts of the image. With a consistent stroke weight and a limited size, the amount of detail must be reduced if you want to obtain a legible result and not a paint stain.
Extracting data by Edge Detection
Extracting relevant information from images to draw outlines and contours using edge detection techniques may be a good idea. Most edge detection techniques produce a blurred image where areas with higher height contrast are shown with a gray scale or a color code corresponding to the direction of the edge.
Even after applying common filtering techniques, as
Bilateral filter, the lines are still not perfectly defined and the edges are blurry. Common approaches like the
Sobel Feldman operator produce a blurry result. After filtering, the edges will become a blob that does not describe the borders in terms of data.
SVG Tracing approach
Standar svg tracing algorithms follow the same steps for converting common color areas into vector shapes. The standard image tracing algorithms, trace the outline borders of color blobs.
When this technique is applied to photographs, it results in a bunch of dots and disjointed shapes. On illustrations and text, svg tracing will produce a double outline that describes the contour of the image lines (blob), making the drone pass twice the same path.
Morphological Skeleton or
Thinning are operations that are used to remove selected foreground pixels from binary images, reducing a blob width to a single pixel line width, can be used to find the trace that forms a stroke.
The issue with these techniques, is that the methods will be performed on all kinds of images without differentiating between strokes and actual shapes. On those cases where the shape width is wider than the output stroke the result will not correlate with the original image.
Abstraction by Canny Edge Detector
Canny is a great technique to obtain a filtered edge detection. The canny approach uses several techniques of filtering and post processing for cleaning and reduces drastically the amount of information, leaving a single pixel border. When parameters are adjusted correctly, an elementary version of the shapes, can be obtained.
This lines are a good abstraction of the complexity of the image.
Illustrations and text require a different kind of pre-processing and filtering. Any tracing or edge detection technique applied over this kind of images will produce a double outline that describes the contour of the image lines.
Morphological Skeleton will create a single-pixel line, but will damage the silhouette of bigger shapes and contours. To solve this obstacle I implemented a combination of operations, using Dilation and the Zhang Suen thinning, that will convert the large shapes into outlines and keep the fine lines as they are. The threshold of this thickness is set at the diameter of the drone’s painting diameter.
|Edge detection||Dilation||Screen (Dilation /-/ threshold)||Zhang-Suen Thinning|
The process of Canny Edge Detection algorithm can be broken down to these steps.
- Gaussian filter
- Gradients (magnitude [x,y])
- Nonmaximum supression
Canny Edge Detection was implemented step by step, tweaking each operation while optimizing the performance to get the best possible results.
Among some optimizations, StackBlur was used for a fast
Gaussian Blur operation.
Applying different kernels and threshold levels allows the tool to extract more or less detail from the original image while maintaining meaning.
|Gaussian filter||Gradients||n-m supression||Hysterysis|
In the conventional way of converting bitmaps to vectors, the tracing operation breaks down into the following steps.
color quantification >
path scan >
inter nodes >
batch trace paths
Since the tool is designed to work only with one color and the previous operations are based on binary maps, the
color quantification is not needed and instead, the result matrix from previous operations is injected into the tracing pipeline.
To generate realistic trajectories that can be reproduced by the drones, the resulting vector paths are filtered to meet the limitations of accuracy, angle precision and minimum distances.
The code of the project was published under the MIT License and you can find it at the Drone-Graffiti github page.