I am attempting to write an algorithm to subdivide a black and white image into image clusters, that maximally omit white space. The practical use case is to do laser rastering more efficiently. (https://github.com/meerk40t/meerk40t/issues/500)
- White edges of an image are omitted by the code already. Only white space between two black dots in a horizontal scanline is wasted.
- Only black pixels need to be lasered.
- By default the rastering process goes entirely across the image (except for white space at edges and entirely white scanlines).
- There is some cost to the extra raster. 140ms per scanline, average rastering would be done around 150mm/s so performing two rasters with the same but shorter scanlines would need to remove about 2.1 cm per scanline to be worth subdividing the raster.
- Overlapping images is fine so long as the black pixel is assigned to only one image.
For example if I have a black frame around white center. It would be highly efficient to cut the image into 4 rectangular parts with each rect covering one side of the frame.
Images which contain a lot of white space or consists of something like
... could be done much better doing 3 rasters; one for each ellipse. By default the raster will go across the entire width of the image.
Is there a name for this algorithm with some solid theory behind it already? Is there an easy solution for this? While K-means clustering with each pixel being a element might work for the circles it seems like it would fail with regard to a frame. And standard euclidean distance is different than clustering into images.
Python using Pillow would be preferred but any algorithm that somewhat reasonably solves this problem would be greatly appreciated.