在2020年春天的大部分时间里，我个人都一无是处。然而，有一段时间，在纽约市冠状病毒病例达到顶峰之后，在纽约市发生警察暴力事件之前，我设法找到了做一些事情的动机，而不是喝酒，疯狂地刷新我的Twitter订阅。我开始做一些完全没有意义的事情。在一个没有任何价值的项目上工作几乎是一种治疗(在这里插入博士笑话)。
我在大学和研究生院度过了10年，收入有限，其中6年是在昂贵的垃圾纽约度过的，这带来的一个副作用是，我吃了很多便宜的三明治，尽管我现在有一份不错的科技™工作。虽然我的三明治消费是相当令人敬畏的前期性爱，但在适当的地方避难巩固了我饮食中的这一主食。我特别喜欢花生酱和香蕉三明治，这是我小时候由经常吃花生酱和香蕉三明治的外祖父介绍给我的。
我把花生酱涂在两片面包上，开始做花生酱香蕉三明治。然后我把香蕉切成圆形，从香蕉的末端开始，然后把每一片放在一片面包上，直到我有一层香蕉片。每次我这样做的时候，我身上那个曾经的凝聚态物理学家就会开始抽搐他的眼睛。你看，我有一种冲动，有一种愿望，有一种需要，就是最大限度地提高香蕉片的包装率。也就是说，我想最大限度地覆盖面包上的香蕉片。就像碗状食物是完美的，因为你每一口都有每一种配料，我的三明治每一口都应该产生相同的黄金比例，即面包、花生酱和香蕉。
如果你是一个机器学习模型(或者我的妻子)，那么你会告诉我只需要沿着香蕉的长轴切割长长的长条，但我不是一个反社会的人。如果生活很简单，那么香蕉片就会是直径相等的完美圆形，我们就可以在狂欢症上寻找最佳的配置。但是，唉，生活并不简单。我们正处于一场全球大流行之中，香蕉片呈椭圆形，大小不一。
那么，我们怎样才能做出最理想的花生酱和香蕉三明治呢？这真的很简单。你拍了一张香蕉和面包的照片，通过深度学习模型传递图像来定位上述物品，对香蕉进行一些非线性曲线拟合，转换到极坐标并沿着拟合的曲线对香蕉进行“切片”，将这些切片变成椭圆多边形，然后将多边形和面包“盒子”送入2D嵌套算法。
你可能已经注意到了，我应该是在春天开始这个项目的，现在已经是8月了。像大多数愚蠢的工程师一样，我不知道这个愚蠢的项目会有多么复杂，但在隔离中时间是没有意义的，所以我们就在这里。然后你就来了！因为如果你想优化你自己的三明治，我做了一个pip可安装的python包nannernest，我将在这篇文章剩下的时间里描述这个该死的东西是如何工作的。
我知道当这个项目最简单的部分是识别图像中属于香蕉或面包片的每个像素时，深度学习已经被适当地商品化了。说真的，这一步超级简单。我使用的是带有RESNET主干的预先训练的Mask-RCNN火炬视觉模型。该模型是在可可数据集上预先训练的，谢天谢地，该数据集有“香蕉”作为分割类别，以及“三明治”和“蛋糕”，这两个类别足够接近，可以适当地检测大多数面包片。
通过模型传递图像输出一串检测到的对象，其中每个检测到的对象具有相关联的标签、分数、边界框和遮罩，其中遮罩标识对应于对象的像素，其中每个像素处的权重对应于模型在该像素的标签中的置信度。
因为图像中可能有多个香蕉和面包片，所以我挑选出得分最高的香蕉和面包片。下面，你可以看到模型能够清楚地识别香蕉和面包，面罩上覆盖着半透明的、具有放射性的绿色。
%config InlineBackend。Figure_format='；retina'；从pathlib导入路径导入matplotlib.pylot作为PLT导入数值作为NP导入nannernest_RC_params={"；figure.figsize"；：(8，4)，"；axes.labelsize"；：16，"；axes.titlesize"；：18，"；axes.spines.right"；：false，"。：false，"；font.size"；：14，"；lines.linewidth"；：2，"；lines.markersize"；：6，"；legend.fontsize"；：14，}表示k，v in_rc_params。项目()：PLT。RcParams[k]=v DPI=160。
既然我们已经识别了图像中的香蕉，我们需要虚拟地“切片”它。这就是我们第一次被介绍到计算机视觉的普遍痛苦的地方：
通过眼睛，我可以确切地看到我想要做的事情；通过代码，这是非常困难的。
我可以让你在香蕉上画几条线，标明你要把它切到哪里，这样你就可以很容易地画出间隔均匀、有点平行的切片。使用代码实现这一点并不容易。然而，我也认为这是问题的有趣之处。有很多方法可以解决这个问题，而且感觉很有创意，而不是使用预先培训的深度学习模型。另一方面，与基于数百万个例子训练的深度学习模型相比，“创造性地”解决这些问题可能会导致更脆弱的解决方案。这里有一个权衡。
我尝试了一系列基于椭圆的分析解决方案，但似乎都不能很好地工作。我最终找到了一个稍微简单一些的解决方案，它可能对普通的香蕉来说并不健壮，但谁在乎呢--这无论如何都是一个愚蠢的项目。使用出色的SCRKIT-IMAGE库，我首先计算了香蕉分割掩模的骨架。这将遮罩减少到一个像素宽的表示，从而有效地创建了一条沿香蕉长轴延伸的曲线。
然后，我使用我在这里找到的基于Scipy的最小二乘优化将圆拟合到香蕉骨架上。实际上，我最初试图将其与PyTorch相匹配，但完全失败了，可能是因为这实际上是一个非线性优化问题。
随着圆与香蕉的适配，现在的目标是绘制从圆中心到香蕉的径向线，并使每条径向线与刀片相对应。同样，虽然很容易想象这一点，但在实践中却难得多。例如，我们需要从香蕉的一端开始切片，但是如何找到香蕉的一端呢？此外，有两个末端，我们必须区分它们。与猴子的行为相反，我从香蕉茎端开始切香蕉，这就是我们现在要做的。
至关重要的是，因为我们现在有了这个圆，并且想要切割径向切片，所以我们必须从笛卡尔坐标转换到极坐标，并相对于香蕉进行径向和角度的定位。作为角度定向的开始，我们计算香蕉遮罩的质心，如果香蕉遮罩是2D对象，则该质心对应于香蕉遮罩的质心。质心在下面显示为一个红点。
现在，我们绘制一条从香蕉圆开始并通过质心的放射线，如下面的白虚线所示。我们将考虑这条线来标记我们的参考角，该参考角将我们定向到香蕉的中心。
AX=Nannernest。也就是。Plot(image，banana_framework=BANANA_SKOLEN，BANANA_COUNTRY=BANANA_COUNTRY，BANANA_CENTROID=BANANA_CENTROID，SHOW=FALSE，dpi=DPI，)dy=BANANA_CENTROID[0]-BANANA_COUND。YC dx=香蕉质心[1]-香蕉圆。XC REFERENCE_ANGLE=NP。圆弧2(dy，dx)半径=Np。Sqrt(dx**2+dy**2)Radial_End_point=(香蕉圈。XC+2*半径*Np。COS(REFERENCE_ANGLE)、BANANA_COLOR。YC+2*半径*Np。Sin(REFERENCE_ANGLE)，)AX。Plot((香蕉圈。Xc，RADIUS_END_POINT[0])，(香蕉圆。YC，RADIUS_END_POINT[1])，颜色="；白色"；，线型="；--"；，线宽=1，)无。
使用SCRKIT-IMAGE，我们使用profile_line函数计算沿径向线的分割掩模强度。因为我们的线沿离散的遮罩像素(也称为矩阵条目)以一定角度通过，所以我们使用line width参数计算沿径向线切割的邻近点的平均值。如你所见，香蕉面具从香蕉圆中心弹出100多点。
这条轮廓线让我们可以径向定位自己。你可以清楚地看到香蕉在径向的起点和终点。像往常一样，仅仅看到它是不够的。我们需要代码来定义香蕉在这个方向上的开始和结束。遮罩倾向于分别沿开始和结束单调增加，然后单调减少。使用这些信息，我们可以用几种方式来定义开始和结束。如果轮廓线的最陡峭部分出现在起点和终点，则起点和终点将分别对应最大导数和最小导数。当模型置信度较低时，我有点担心遮罩信号中的噪声，因此我首先数字化(或阈值)轮廓线，如果轮廓线小于(大于)0.5，则将其设置为0(1)。
数字化=PROFILE_LINE>；0.5图，AX=PLT。SUBPLETS()AX。绘制(PROFILE_LINE，LABEL="；RAW PROFILE"；)AX。Plot(数字化，"；--"；，标签="；数字化"；)轴。图例()斧头。设置_xlabel("；到香蕉圆中心的距离"；)轴。SET_TITLE("；蒙版强度"；)无。
现在，我们根据数字化信号的最大和最小导数来搜索信号翻转的点。这可以通过一些快速麻木来完成。这仍然是一个危险的(引用：“危险”，这是一个香蕉)的操作，可能会放大噪音。将来的一种选择是在取导数之前平滑轮廓线。
无花果，AX=PLT。SUBPLETS()AX。打印(PROFILE_LINE)AX。绘制((START，START)，(0，1)，"；k--"；)AX.。Plot((end，end)，(0，1)，"；k--"；)ax.。注释("；开始"；，(开始，1)，ha="；right"；，va="；center"；)ax。注释("；End"；，(End，1)，ha="；Left"；，va="；Center"；)ax.。设置_xlabel("；到香蕉圆中心的距离"；)轴。SET_TITLE("；蒙版强度"；)无
我们现在可以相对于香蕉的中心成角度地定位自己，并根据香蕉的起点和终点沿径向线进行径向定位。最后一步是查找香蕉的角度起点和终点，其中角度起点将对应于指向香蕉茎的角度。为此，我们首先创建一个角度数组，范围从参考质心角度减135$^{\CIRC}$到参考角度加135$^{\CIRC}$。类似于numpy的linspace，我们将此数组称为$\phi$-space。
对于$\φ$-space中的每个角度，我们将像上面一样计算一条轮廓线。下面，我们创建一个201点的$\φ$-空间，并在原始图像上绘制这些轮廓线中的每一条。你可以看到，它们清楚地覆盖着香蕉，两边都有一些健康的空间。
AX=Nannernest。也就是。为phi_space中的phi绘制(image，banana_framework=banana_framework，banana_Circle=banana_Circle，banana_centroid=banana_centroid，show=false，dpi=dpi，)：Radial_End_point=(Banana_Circle)。(BANANA_CENTROID=BANANA_CENTROID，show=false，dpi=DPI，)。XC+2*半径*Np。Cos(φ)，香蕉圈。YC+2*半径*Np。Sin(Phi)，)ax.。Plot((香蕉圈。Xc，RADIUS_END_POINT[0])，(香蕉圆。YC，RADIUS_END_POINT[1])，颜色="；白色"；，线型="；--"；，线宽=0.5，)。
我们还可以将所有轮廓线彼此堆叠在一起，这样我们就有了一个矩阵，其中行是角度，列表示径向距离，值是沿着这些线的遮罩强度。下面这个矩阵的假彩色图显示了香蕉。香蕉的长轴大致沿着$\φ$空间方向。顶部的一小块香蕉与香蕉茎相对应。$\φ$-空间角度是相对于水平轴的。
无花果，AX=PLT。子图(figsize=(10，10))im=ax。Imshow(配置文件)AX。Set_xlabel("；Radius"；)AX。Set_ylabel("；$\phi$-space(度)"；)ticks=np。Linspace(0，len(Phi_Space)-1，11，dtype=np.。(三)斧头。Set_yticks(刻度)轴。Set_yticklabels((φ_space[刻度]*180/nP。PI)。Astype(Int))PLT。Colorbar(im，cax=图。添加轴([0.93，0.3，0.03，0.4]))无。
最后，有了上面这个奇特的矩阵，它代表了这个扭曲到笛卡尔地块上的极地世界，我们可以同时识别香蕉茎和香蕉种子所在的另一端。我找香蕉的两端使用了与前面类似的方法，找出香蕉的径向起点和终点。然后我找出香蕉两端周围区域的平均遮罩强度，并假设茎的平均强度较小。最后，我使用香蕉种子侧应该具有与茎侧无茎相似的平均强度的知识，几乎“砍掉”了茎。
完成这项工作后，我现在已经确定了香蕉茎和种子的角度位置，以及香蕉在任何角度上的径向起点和终点。我把香蕉切成等间距的角，然后在每个角的间距上画一个长方形的切片。我将切片总数作为自由参数保留，它隐式地确定了香蕉切片厚度。默认情况下，我切23片，然后扔掉第一片和最后一片(没人想要这些)。
我们现在必须对香蕉片做两个假设。首先，我们知道香蕉片会比上面显示的要小，因为香蕉皮的厚度是有限的。其次，香蕉不是完美的圆形，切成的薄片会变成椭圆形。根据用卷尺(我没有卡钳)的几个糟糕的测量结果，我假设实际的香蕉片比上面用香蕉皮拍摄的图片小20%。我还使用上图中的切片来表示香蕉切片椭圆的长轴，并假设短轴是长轴大小的85%。
无花果，AX=PLT。子图(figsize=(8，8))θ=Np。线性空间(0，2*np.。PI，101)斧头。Plot((Slices[0]。MAJOR_AXIS/2)*NP。Cos(Theta)，(Slices[0].。Minor_Axis/2)*NP。Sin(Theta)，)LIM=Slices[0]。长轴/2+1轴。Set_xlim((-LIM，LIM))AX。Set_ylim((-LIM，LIM))无。
在这条长得离谱的管道的最后一步之前，我们必须将椭圆形切片转换为多边形。从技术上讲，上面的地块是一组离散的点，可以认为是一个多边形。不过，为了使问题易于处理，我们将椭圆缩减为一小组点。当我第一次开始解决这个问题时，我不知道我是否会在为每个切片多边形分配多少点方面受到严重限制。我还有点神经质(轻描淡写)，担心多边形的大小不一定与椭圆完全相同。
为了解决这个问题，我想要计算出外接椭圆的多边形。我很惊讶没有找到这方面的任何代码，所以我最终试图用解析的方式解决它。生成的代数相当粗糙，所以现在Nannernest中有一个函数，它运行渐近，并根据椭圆多边形中的点数计算长轴和短轴的比例因子。
下面，我为一个12点的多边形绘制椭圆和外接多边形。虽然(根据定义)外接多边形比椭圆大，但差别很小。我可能只需要把原来的椭圆切成12个点而不会有太大的精确度损失。实际上，我一直在使用30分，这只会让差异变得更小。另外，FWIW，我认为我的代数只有在x轴和y轴上有多边形点的情况下才起作用，所以这就对了。如果有人对此有封闭形式的解决方案，我很乐意看到！
无花果，AX=PLT。子图(figsize=(8，8))θ=Np。线性空间(0，2*np.。Pi，101)Slice_x=(Slices[0]。MAJOR_AXIS/2)*NP。Cos(Theta)Slice_y=(Slices[0]。Minor_Axis/2)*NP。罪恶(θ)斧头。Plot(Slice_x，Slice_y)LIM=max(Slice_x.。Max()，Slice_y。Max())+5 NUM_POINTS=12 MAJOR_SCALER，MINOR_SCALER=nannernest。筑巢。Calc_Elltical_Polygon_Scalers(Num_Points)poly=nannernest。筑巢。Ellipse_to_Polygon(Slices[0]，Num_Points，MAJOR_SCALER，MINOR_SCALER)AX。Plot(*zip(*poly)，"；o--"；)ax。Set_xlim((-LIM，LIM))AX。Set_ylim((-LIM，LIM))无。
这部分相当快。我需要把面包定义为一个“盒子”，在里面安放我的香蕉片。最初，我只是使用分割算法中的边界框。但是，边界框仅定义面包的最大边界。一时兴起，我尝试将图像旋转30$^{\cic}$(抱歉，我执行了“数据增强”)，我发现边界框没有随面包一起旋转。谢天谢地，我有了分段掩码，我抓取了一个旋转卡尺的python实现，以找到包含该掩码的最小区域边界框。
当我最终拿到从图像中提取的多边形椭圆形香蕉片和一个漂亮的面包盒时，我以为我会自由地回家。当然，有一个简单的算法，我可以将多边形和方框插入其中，以最大化覆盖范围？原来，这种通常被称为“嵌套”或“打包”的问题是极其困难的。就像NP-Hard一样。令人惊讶的是，这是一个热门的研究领域，因为有一大堆应用程序。紧密堆积多边形类似于在使用CNC机床切割金属薄板或从织物上裁剪服装图案时尝试使用最多的材料。我甚至看到，嵌套椭圆的应用需要将染料注入大脑进行成像。染料呈椭圆形展开，人们希望用最少的注射次数获得最大的覆盖率。
我最初打算找到一个将椭圆打包在盒子中的解析解决方案，但这似乎并不真正存在。随着时间的推移，我满足于在盒子中嵌套多边形的任何像样的解决方案。流行的解决方案往往涉及在框中一次放置一个多边形。每个多边形都与前一个多边形接触。人们通常从盒子的一角开始，一排一排地装满它。这听起来很简单，但是您必须构建一组代码来接触两个多边形，而不会重叠。也可以旋转多边形，按您想要的任何顺序放置，等等…。组合搜索空间巨大，因此人们通常采用以下优化方法
找到一种快速方法来确定两个多边形可以接触的所有可能点。这是通过不拟合面完成的。
定义一个总体目标，然后使用黑盒优化器更有效地搜索空间。空间涉及多边形放置的顺序和多边形放置时的角度等问题。
几个月来，我在寻找吉斯之间摇摆不定。
.