Thread by @doctorow

For those of us who use work to cope with stress and anxiety with work, the plague months have been an oddly productive time.

For data scientist @eprosenthal, it was an opportunity to optimize his banana-sandwich process.

ethanrosenthal.com/2020/08/25/opt…

1/

Rosenthal's ideal peanut-butter and banana sandwich is calibrated to have precisely the same amount of banana in every mouthful.

Naturally, Rosenthal eschews obviously incorrect solutions to this like mashing the banana or cutting it into lengthwise, rectangular slices.

2/

Rosenthal wants to figure out how to cut banana cross-sections and then arrange them such that they cover as much of the bread-slice as possible without overlapping ("maximizing the packing fraction"). And he used machine learning to do it.

3/

The pretrained Mask-RCNN torchvision model (with a Resnet backbone) made it easy to detect and measure a banana and a slice of bread from a photo. Applying the scikit-image library allows him to calculate a "skeleton" for the banana that corresponds to its curvature.

4/

A scipy-based least squares optimization fits a circle to the skeleton. From there, compute a "centroid" for the banana ("which corresponds to the center of mass of the banana mask if the banana mask were a 2D object") and create a reference angle for a radial transection.

5/

Scikit-image's profile_line function allows for a radial orientation, the first step towards identifying the seed- and stem-ends of the banana.

6/

Now that the model is oriented "angularly with respect to the center of the banana and radially in terms of the start and end of the banana along the radial line," he computes the angular start and end of the banana.

7/

All that remains is to slice the banana into "evenly spaced angles and drawing a rectangular slice at each angle spacing." Adjust the resulting ellipses to account for the peel-thickness, convert to polygons, and you're in business.

8/

Despite being a pretty simple rectangle, the bread still needs some computational work, but it's pretty simple (the key is using a python-based rotating calipers on the segmentation mask). Now you've got a clean bread-box and polygonal, ellipsoidal banana slices.

9/

There's only one problem: fitting a bunch of arbitrary polygons into a box is NP -hard or maybe NP-complete - that is, the ideal solution is uncomputable (similar to the "traveling salesman" and "knapsack" problems).

10/

Rosenthal's best-fit solution recursively applies nest2D and comes up with a good approximation of an optimal solution in finite time.

11/

He's packaged the result in a command-line package called "nannernest" that takes a JPEG as its sole argument and spits out an optimal slice-and-arrange pattern for any given banana and bread-slice.

Just look at it.

eof/