在保留轮廓形状的同时压缩稀疏矩阵
Compacting a sparse matrix while preserving outline shape
我正在寻找一种方法来压缩稀疏矩阵，同时保留其轮廓的形状和（尽可能）非零点之间的相对距离。因此，以图形方式展示我想要得到的东西：
对于给定的矩阵：
0 0 1 0 0
1 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 0 0 1
我希望得到以下矩阵之一：
0 1 0 1 1 0 1 1 0
1 1 1 0 1 1 1 1 0
0 1 1 0 1 1 1 0 1
当然这里可以有更多解法，没有"better"解法，只要算法一致即可。我正在使用的矩阵是 1024x1024 和 15-30k 非零点。非零点是我在 1024x1024 图像中识别的特征中心。我正在尝试生成这些特征的密集矩阵。
我尝试了 kD 树方法，我计算了每个非零点的 n 个最近邻居。然后，我以随机顺序访问每个非零点，并将其最近的邻居放置在 3x3 矩阵中的适当位置，当前点位于中心。这以某种方式起作用，但导致仍然非常稀疏的矩阵和许多岛屿。接受多个邻居导致合并不一致。
是否有一些标准的方法来做我想做的事情？我是不是漏掉了一些非常标准的算法？
你们知道什么是解决我的问题的全局优化的好方法吗？
我现在正在 Python 中实现此功能（使用 numpy），但我将不胜感激任何其他语言的任何通用算法建议或实现...
提前致谢！
编辑 1：
这里是 a gist 我到目前为止所写的内容。通过严格检查每个点的邻域，我设法避免了邻居冲突，但我发现有些点被从最终矩阵中剔除了。整个过程太慢了...
输入为以下格式的 CSV（目前只有 cx 和 cy 重要）：
ParticleID,cx,cy,cz,Volume,Integral 0,Mean 0,Integral 1,Mean 1
编辑 2：
对 Jerry 的回答的一些评论：
1）我想我没有明确说明我的主要目标：主要目标是确保最大数量的点被8个邻居包围，而不会对轮廓或初始相对的整体形状造成严重扭曲点位
2)缩放图像的想法似乎是一个解决方案，但我应该缩放多少？如何确定最佳比例因子？我不想将图像缩放到特定大小。我想删除图像中非零点之间的空白区域。
这是两个 objective 的优化问题：边界框大小和误差（相对距离）。因此，您获得了可能解决方案的帕累托前沿，每个解决方案都针对边界框大小与误差的不同权衡进行了优化。
如果您对其中一个 objective 设置一个界限，然后在给定该界限的情况下，只在另一个 objective 上尽可能地解决问题，问题就会简单得多。所以你可以说 "given a particular bounding box size, how can I minimize the error?" 或 "given a maximum acceptable error, how can I minimize the bounding box size?"
我假设您更可能想到特定的边界框大小，而不是特定的最大误差，所以让我们从假设一个边界框开始，并尝试将分配点的错误最小化该边界框中的独特位置。
您需要使用一种优化技术来很好地处理您的问题的离散特征。我会选择模拟退火。
从好种子开始
给定边界框大小，您可以将整个图像缩小到边界框大小...但有些点最终会位于相同位置。称之为“朴素定位”：
.........................................
. . . . .
. . 2 3 . . .
. 1 . . . 4 .
.........................................
. . . . .
. . . . .
. . . . .
.........................................
. . . . .
. . . . .
. . 5 . . 6 .
.........................................
. 7 . . . .
. 8 . . . .
. . . . .
.........................................
好的，我们可以处理这个问题。为您的头寸定义一个顺序。您可以天真地（从左到右，从上到下）或以更好地保留局部性的方式（希尔伯特曲线）执行此操作。我们将遍历这些位置，当我们找到一个位置超过一个点时，尝试在有意义的时候将额外的点分配给可用的空位置。
Keep a queue of DisplacedPoints
Keep a stack of EmptyPositions
Iterate over positions in the order you've chosen:
If this position is empty,
Push this position onto EmptyPositions
Else If this position has more than one point,
Enqueue all but one of these points into DisplacedPoints
Placement: While there are remaining DisplacedPoints and remaining EmptyPositions,
Let candidatePoint = DiplacedPoints.Peek
Let candidatePosition = EmptyPositions.Peek
Let currentDisplacement = the distance from the current position to candidatePoint's naive position
Let candidateDisplacement = the distance from candidatePosition to candidatePoint's naive position
If currentDisplacement >= candidateDisplacement,
place candidatePoint in candidatePosition
pop candidatePosition off EmptyPositions
dequeue candidatePoint off DisplacedPoints
Else break out of Placement loop
While there are remaining DisplacedPoints and remaining EmptyPositions,
Dequeue a DisplacedPoint D, pop an EmptyPosition E, and put D into E
如果这太复杂了，一个更简单的方法就是遍历位置；当你遇到一个有太多点的位置时，将多余的点入队，当你遇到一个空位置时，将一个点出队到其中。如果你到达终点并且队列中仍有点，则向后迭代这些位置（不再有超过一个点的位置）并将点出队到空白处。
无论如何这都不是最佳解决方案。这只是一个很好的初步猜测，可以让模拟退火有一个好的开始。
Objective函数性能
朴素的 objective 函数类似于（原始图像中点之间的距离）和（缩放后的点之间的距离）之间的平方差之和（在所有点对上）向下图像，乘以缩放因子）。但是对于 20k 点，这大约是 4 亿平方差！我们可以通过从一个愚蠢但快速的 objective 函数开始取得初步进展，然后切换到更昂贵（和正确）的函数来获得更精细的区别，从而更快地收敛到一个好的解决方案。
您可以使用的最快、最愚蠢的 objective 函数是 O(n)：将所有点与它们自己的距离相加 朴素定位 .
一个更慢但更正确的 objective 函数分配每个点 "relevant neighbors"：对于每个点 P，我们将采用 P 的原始定位周围位置的 3x3 邻域中的点*。现在，您可以对所有点 P 求和（在 P 的所有相关邻居上）图像距离与（缩放的）指定位置距离之间的平方差。
*由于A到B的距离与B到A的距离相同，一旦点X是P的相关邻居之一，我们就不必认为P是X的相关邻居之一.利用它可以实现 2 倍的加速。
在那些更快的 objective 函数让你更接近最佳之后，你可以使用上面列出的朴素 objective 函数（对所有对的距离平方差求和）。我不确定您是否真的想要这个 - 天真的 objective 函数想要保留长距离结构，但您可能只关心保留邻居之间的距离。
编辑：重新缩放的总体思路应该可行，但与其进行天真的重新缩放然后在事后进行调整，另一种方法是使重新缩放本身更智能。
考虑使用 Content-Aware Scaling。在水平和垂直缩放之间反复交替，以保持整体形状尽可能接近原始形状。
要保持附近点之间的空间关系，您可以调整接缝生成中使用的能量函数。首先将值 1.0 分配给有点的位置，将 0.0 分配给没有点的位置，然后应用高斯模糊。这将导致接缝生成在开始折叠附近点之间的小空间之前更喜欢切出大的空白空间。
如果这太昂贵/太复杂，您可以尝试更简单的方法：
以你原来的例子为例（赋予点不同的身份）：
0 0 1 0 0
2 0 0 0 0
0 3 0 4 0
0 0 0 0 0
0 5 0 0 6
找到你的点的平均 x 和 y 坐标。在此示例中，平均位置位于 3 的右下角。从逻辑上将您的数组分成四个象限，这些象限在平均位置相遇。
0 0|1 0 0
2 0|0 0 0
0_3|0_4_0
0 0|0 0 0
0 5|0 0 6
现在可以独立处理每个象限。在每个象限中，有两个指向中心的网格对齐方向（例如，在左上象限中，向下和向右指向中心）。我们在这两个方向之间交替，将点移动到相邻的空白区域。如果两个方向都没有改善，那么您就完成了该象限。
因此，以右上象限为例，我们将点数向下移动...
0 0|0 0 0
2 0|1 0 0
0_3|0_4_0
0 0|0 0 0
0 5|0 0 6
请注意，我们不会将 4 推过象限边界。然后，我们尝试向左推：
0 0|0 0 0
2 0|1 0 0
0_3|4_0_0
0 0|0 0 0
0 5|0 0 6
然后我们尝试向下推，但实际上没有任何动静。尝试向左移动，但仍然没有动静。右上象限已完成。其他象限也照样做：
0 0|0 0 0
0 2|1 0 0
0_3|4_0_0
0 5|6 0 0
0 0|0 0 0
现在，找到点和裁剪的边界框：
2 1
3 4
5 6
我正在寻找一种方法来压缩稀疏矩阵，同时保留其轮廓的形状和（尽可能）非零点之间的相对距离。因此，以图形方式展示我想要得到的东西：
对于给定的矩阵：
0 0 1 0 0
1 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 0 0 1
我希望得到以下矩阵之一：
0 1 0 1 1 0 1 1 0
1 1 1 0 1 1 1 1 0
0 1 1 0 1 1 1 0 1
当然这里可以有更多解法，没有"better"解法，只要算法一致即可。我正在使用的矩阵是 1024x1024 和 15-30k 非零点。非零点是我在 1024x1024 图像中识别的特征中心。我正在尝试生成这些特征的密集矩阵。
我尝试了 kD 树方法，我计算了每个非零点的 n 个最近邻居。然后，我以随机顺序访问每个非零点，并将其最近的邻居放置在 3x3 矩阵中的适当位置，当前点位于中心。这以某种方式起作用，但导致仍然非常稀疏的矩阵和许多岛屿。接受多个邻居导致合并不一致。
是否有一些标准的方法来做我想做的事情？我是不是漏掉了一些非常标准的算法？
你们知道什么是解决我的问题的全局优化的好方法吗？
我现在正在 Python 中实现此功能（使用 numpy），但我将不胜感激任何其他语言的任何通用算法建议或实现...
提前致谢！
编辑 1：
这里是 a gist 我到目前为止所写的内容。通过严格检查每个点的邻域，我设法避免了邻居冲突，但我发现有些点被从最终矩阵中剔除了。整个过程太慢了...
输入为以下格式的 CSV（目前只有 cx 和 cy 重要）：
ParticleID,cx,cy,cz,Volume,Integral 0,Mean 0,Integral 1,Mean 1
编辑 2： 对 Jerry 的回答的一些评论：
1）我想我没有明确说明我的主要目标：主要目标是确保最大数量的点被8个邻居包围，而不会对轮廓或初始相对的整体形状造成严重扭曲点位
2)缩放图像的想法似乎是一个解决方案，但我应该缩放多少？如何确定最佳比例因子？我不想将图像缩放到特定大小。我想删除图像中非零点之间的空白区域。
这是两个 objective 的优化问题：边界框大小和误差（相对距离）。因此，您获得了可能解决方案的帕累托前沿，每个解决方案都针对边界框大小与误差的不同权衡进行了优化。
如果您对其中一个 objective 设置一个界限，然后在给定该界限的情况下，只在另一个 objective 上尽可能地解决问题，问题就会简单得多。所以你可以说 "given a particular bounding box size, how can I minimize the error?" 或 "given a maximum acceptable error, how can I minimize the bounding box size?"
我假设您更可能想到特定的边界框大小，而不是特定的最大误差，所以让我们从假设一个边界框开始，并尝试将分配点的错误最小化该边界框中的独特位置。
您需要使用一种优化技术来很好地处理您的问题的离散特征。我会选择模拟退火。
从好种子开始
给定边界框大小，您可以将整个图像缩小到边界框大小...但有些点最终会位于相同位置。称之为“朴素定位”：
.........................................
. . . . .
. . 2 3 . . .
. 1 . . . 4 .
.........................................
. . . . .
. . . . .
. . . . .
.........................................
. . . . .
. . . . .
. . 5 . . 6 .
.........................................
. 7 . . . .
. 8 . . . .
. . . . .
.........................................
好的，我们可以处理这个问题。为您的头寸定义一个顺序。您可以天真地（从左到右，从上到下）或以更好地保留局部性的方式（希尔伯特曲线）执行此操作。我们将遍历这些位置，当我们找到一个位置超过一个点时，尝试在有意义的时候将额外的点分配给可用的空位置。
Keep a queue of DisplacedPoints
Keep a stack of EmptyPositions
Iterate over positions in the order you've chosen:
If this position is empty,
Push this position onto EmptyPositions
Else If this position has more than one point,
Enqueue all but one of these points into DisplacedPoints
Placement: While there are remaining DisplacedPoints and remaining EmptyPositions,
Let candidatePoint = DiplacedPoints.Peek
Let candidatePosition = EmptyPositions.Peek
Let currentDisplacement = the distance from the current position to candidatePoint's naive position
Let candidateDisplacement = the distance from candidatePosition to candidatePoint's naive position
If currentDisplacement >= candidateDisplacement,
place candidatePoint in candidatePosition
pop candidatePosition off EmptyPositions
dequeue candidatePoint off DisplacedPoints
Else break out of Placement loop
While there are remaining DisplacedPoints and remaining EmptyPositions,
Dequeue a DisplacedPoint D, pop an EmptyPosition E, and put D into E
如果这太复杂了，一个更简单的方法就是遍历位置；当你遇到一个有太多点的位置时，将多余的点入队，当你遇到一个空位置时，将一个点出队到其中。如果你到达终点并且队列中仍有点，则向后迭代这些位置（不再有超过一个点的位置）并将点出队到空白处。
无论如何这都不是最佳解决方案。这只是一个很好的初步猜测，可以让模拟退火有一个好的开始。
Objective函数性能
朴素的 objective 函数类似于（原始图像中点之间的距离）和（缩放后的点之间的距离）之间的平方差之和（在所有点对上）向下图像，乘以缩放因子）。但是对于 20k 点，这大约是 4 亿平方差！我们可以通过从一个愚蠢但快速的 objective 函数开始取得初步进展，然后切换到更昂贵（和正确）的函数来获得更精细的区别，从而更快地收敛到一个好的解决方案。
您可以使用的最快、最愚蠢的 objective 函数是 O(n)：将所有点与它们自己的距离相加 朴素定位 .
一个更慢但更正确的 objective 函数分配每个点 "relevant neighbors"：对于每个点 P，我们将采用 P 的原始定位周围位置的 3x3 邻域中的点*。现在，您可以对所有点 P 求和（在 P 的所有相关邻居上）图像距离与（缩放的）指定位置距离之间的平方差。
*由于A到B的距离与B到A的距离相同，一旦点X是P的相关邻居之一，我们就不必认为P是X的相关邻居之一.利用它可以实现 2 倍的加速。
在那些更快的 objective 函数让你更接近最佳之后，你可以使用上面列出的朴素 objective 函数（对所有对的距离平方差求和）。我不确定您是否真的想要这个 - 天真的 objective 函数想要保留长距离结构，但您可能只关心保留邻居之间的距离。
编辑：重新缩放的总体思路应该可行，但与其进行天真的重新缩放然后在事后进行调整，另一种方法是使重新缩放本身更智能。
考虑使用 Content-Aware Scaling。在水平和垂直缩放之间反复交替，以保持整体形状尽可能接近原始形状。
要保持附近点之间的空间关系，您可以调整接缝生成中使用的能量函数。首先将值 1.0 分配给有点的位置，将 0.0 分配给没有点的位置，然后应用高斯模糊。这将导致接缝生成在开始折叠附近点之间的小空间之前更喜欢切出大的空白空间。
如果这太昂贵/太复杂，您可以尝试更简单的方法：
以你原来的例子为例（赋予点不同的身份）：
0 0 1 0 0
2 0 0 0 0
0 3 0 4 0
0 0 0 0 0
0 5 0 0 6
找到你的点的平均 x 和 y 坐标。在此示例中，平均位置位于 3 的右下角。从逻辑上将您的数组分成四个象限，这些象限在平均位置相遇。
0 0|1 0 0
2 0|0 0 0
0_3|0_4_0
0 0|0 0 0
0 5|0 0 6
现在可以独立处理每个象限。在每个象限中，有两个指向中心的网格对齐方向（例如，在左上象限中，向下和向右指向中心）。我们在这两个方向之间交替，将点移动到相邻的空白区域。如果两个方向都没有改善，那么您就完成了该象限。
因此，以右上象限为例，我们将点数向下移动...
0 0|0 0 0
2 0|1 0 0
0_3|0_4_0
0 0|0 0 0
0 5|0 0 6
请注意，我们不会将 4 推过象限边界。然后，我们尝试向左推：
0 0|0 0 0
2 0|1 0 0
0_3|4_0_0
0 0|0 0 0
0 5|0 0 6
然后我们尝试向下推，但实际上没有任何动静。尝试向左移动，但仍然没有动静。右上象限已完成。其他象限也照样做：
0 0|0 0 0
0 2|1 0 0
0_3|4_0_0
0 5|6 0 0
0 0|0 0 0
现在，找到点和裁剪的边界框：
2 1
3 4
5 6