Barrier synchronization is always going to wreck parallel performance. When possible, it's good to break up your work so that data dependencies are explicit and fine grained. So instead of breaking up work like this:<p><pre><code> IIIIJJJJKKKKLLLL
<barrier>
EEEEFFFFGGGGHHHH
<barrier>
AAAABBBBCCCCDDDD
</code></pre>
... where each row is dependent on the entire previous row, break it up like this:<p><pre><code> HHHHIIIIJJJJKKKK
EEEEEEFFFFGGGGGG
AAAABBBBCCCCDDDD
</code></pre>
Where E is dependent on A and B, (and begins when they are done) H is dependent only on E, F is dependent on B and C, etc. This way you don't have to wait for the entire strip to finish, you can start work on E after A+B, but while D is still working. This also gives you weird block sizes for "free", which is a huge no-no with barrier synchronization. For instance, Es and Gs are size 6; if the first example had most elements of size 4, but one element of size 6, it would be catastrophic. All your threads would be done when the final thread is only 66% complete, and it's single threaded from there on out for that strip.
I created a desktop GUI tool [0] that used multiple cores for seam carving images of your choice. Including masking parts of image to keep or remove. The backend code parallelizing the work is from the CAIRE project.<p>It was ages ago, and has since been archived on google code :)<p>[0] <a href="https://code.google.com/archive/p/seam-carving-gui/" rel="nofollow">https://code.google.com/archive/p/seam-carving-gui/</a>
[1] <a href="https://github.com/esimov/caire" rel="nofollow">https://github.com/esimov/caire</a>
This is so cool, it reminds me of this series of responsive pixel art: <a href="https://essenmitsosse.de/pixel/?showcase=true&slide=5" rel="nofollow">https://essenmitsosse.de/pixel/?showcase=true&slide=5</a>
If folks are interested in a simple implementation to read or reuse, here's a JS version I wrote back when HTML5 and <canvas> were new and exciting (over 10 years ago now): <a href="https://nicolasff.github.io/canvas-seam-carving/" rel="nofollow">https://nicolasff.github.io/canvas-seam-carving/</a><p>The button says "warning: very slow" but JavaScript performance has significantly improved since then :-)<p>Still a very cool technique, and pretty easy to implement.
A related idea would be “image summarization”, i.e. an (as-yet hypothetical) technique for generating an image that’s an “icon” of a larger image. In the same sense of “icon” as the one visual designers are trained to create: one where both large-scale structure (shape+color) and fine-scale structure (texture) are preserved, while “redundant” detail is sacrificed, in order of least to most important for visual recognition by a human or image-classifier model. You could also call this a type of <i>psycho-visual</i> compression, in the same vein as chroma subsampling.<p>Simply resampling an image smaller keeps the large-scale structure (the shape and color), but loses the fine-scale structure (texture.) That’s why we don’t just resample photos down to 32x32 and use them as icons :)<p>Seam Carving (whether parallel or not) does the opposite: it preserves the fine-scale structure (texture) but distorts the large-scale structure (shape.)<p>But not always! The amount of shape distortion in Seam Carving is worst case O(N) with the number of seams deleted, but best-case o(1). It depends on the algorithm’s choices of seam.<p>Regular <i>iterative</i> Seam Carving, as described by its original paper, isn’t stateful-enough to be able to minimize any whole-image quality (like loss of large structure.) So it’s no surprise it hasn’t been used for something like this.<p>But <i>parallel</i> Seam Carving might just be the ticket for this problem. A model could be trained to select an optimal set of seams that work together to minimize the large-structure deformation of the image (i.e. the image’s lower-band difference in frequency-space), while also individually being low-entropy seams from the Seam Carving algorithm’s perspective.<p>Anyone want to take a crack at this?
You can divide the work into twice as many independent chunks of the same size like so:<p>If you were going to divide the image into K horizontal strips of triangles, instead divide the top half into K/2 horizontal strips of triangles and divide the bottom half into K/2 horizontal strips of triangles. To make things easier at the end, please include a 1px tall overlap between the top and bottom parts. Work downward from the top and upward from the bottom until you reach the middle. At the middle, for each column, you have the cost of the top half of the minimum seam that includes that pixel and the cost of the bottom half of the minimum seam that includes that pixel. So you can add those together then take the min as before.
Does repeated single-pixel seam-carving minimise energy for the "remove n seams" problem? If not, is the global algorithm in P?<p>Also, I guess this is beside the point, but surely almost all of the DP structure can be reused if you're repeatedly removing seams...
This is probably also a very interesting technique for data augmentation for computer vision ML. (That is, seam carving. Not much to do with the parallel version...)<p>Unlike other typical data augmentation operations, spatial relationships are altered in nonlinear but still realistic ways.