4

假设我们有一个简单的矩阵 3rows x 7cols。该矩阵仅包含零 (0) 和 (1)，例如：

1 0 1 1 1 0 0
0 0 1 1 0 0 0
0 0 1 0 1 1 0

Senario：如果我们知道每一行中非零的总和，

（第一行是 4，第二行是 2，第三行是 3。）（蓝线）

另外，如果我们知道每个 col (1 , 0, 3, 2, 2, 1, 0) 的总和（绿线）

如果我们知道从左上角到右下角（1,0,1,2,3,0,1,1,0）（红线）逆时针方向的每个对角线的总和

最后我们知道从左下角到右上角的每个对角线的总和（0,0,2,1,3,2,1,0,0）（黄线）

在此处输入图像描述

我的问题是：以这些值作为输入（以及矩阵 3x7 的长度），

4, 2, 3
1, 0, 3, 2, 2, 1, 0
1, 0, 1, 2, 3, 0, 1, 1, 0
0, 0, 2, 1, 3, 2, 1, 0, 0

我们如何绘制第一个矩阵？经过深思熟虑，我得出结论，这是一个具有 3x7 未知值和一些方程的线性方程组。正确的？

如何用 C 或其他语言制作算法来求解这些方程？我应该使用像高斯方程这样的方法吗？

任何帮助将不胜感激！

4

4 回答 4

2

您可以使用奇异值分解来计算矩阵形式的线性齐次（和非齐次）方程组的非零最小二乘解。

如需快速概览，请参阅：

http://campar.in.tum.de/twiki/pub/Chair/TeachingWs05ComputerVision/3DCV_svd_000.pdf

您应该首先将您的系统写成 Ax = b 形式的矩阵方程，其中 x 是作为列向量的 21 个未知数，A 是乘以时形成线性系统的 28 x 21 矩阵。您基本上需要计算线性方程的矩阵 A，计算 A 的奇异值分解并将结果代入方程，如方程 9.17 所示

有很多库可以在 C 中为您计算 SVD，因此您只需要制定矩阵并在 9.17 中执行计算。最困难的部分可能是理解它是如何工作的，使用库 SVD 函数需要的代码相对较少。

为了让您开始了解如何形成线性系统方程，请考虑一个简单的 3 x 3 案例。

假设我们的系统是以下形式的矩阵

1 0 1
0 1 0
1 0 1

我们将对线性系统有以下输入：

2 1 2             (sum of rows                 - row)
2 1 2             (sum of colums               - col)
1 0 3 0 1         (sum of first diagonal sets  - t2b)
1 0 3 0 1         (sum of second diagonal sets - b2t)

所以现在我们为线性系统创建一个矩阵

 A            a1 a2 a3 b1 b2 b3 c1 c2 c3     unknowns (x)    =   result (b)
sum of row 1 [ 1  1  1  0  0  0  0  0  0 ]      [a1]                [2]       
sum of row 2 [ 0  0  0  1  1  1  0  0  0 ]      [a2]                [1]
sum of row 3 [ 0  0  0  0  0  0  1  1  1 ]      [a3]                [2]
sum of col 1 [ 1  0  0  1  0  0  1  0  0 ]      [b1]                [2]
sum of col 2 [ 0  1  0  0  1  0  0  1  0 ]      [b2]                [1]
sum of col 3 [ 0  0  1  0  0  1  0  0  1 ]      [b3]                [2]
sum of t2b 1 [ 1  0  0  0  0  0  0  0  0 ]      [c1]                [1]
sum of t2b 2 [ 0  1  0  1  0  0  0  0  0 ]      [c2]                [0]
sum or t2b 3 [ 0  0  1  0  1  0  1  0  0 ]      [c3]                [3]
sum of t2b 4 [ 0  0  0  0  0  1  0  1  0 ]                          [0]
sum of t2b 5 [ 0  0  0  0  0  0  0  0  1 ]                          [1]
sum of b2t 1 [ 0  0  0  0  0  0  1  0  0 ]                          [1]
sum of b2t 2 [ 0  0  0  1  0  0  0  1  0 ]                          [0]
sum of b2t 3 [ 1  0  0  0  1  0  0  0  1 ]                          [3]
sum of b2t 4 [ 0  1  0  0  0  1  0  0  0 ]                          [0]
sum of b2t 5 [ 0  0  1  0  0  0  0  0  0 ]                          [1]

当你乘以 Ax 时，你会看到你得到了线性方程组。例如，如果你将第一行乘以未知列，你会得到

a1 + a2 + a3 = 2

您所要做的就是在方程中出现的任何列中输入 1，在其他地方输入 0。

现在您所要做的就是计算 A 的 SVD 并将结果代入方程 9.17 以计算未知数。

我推荐 SVD，因为它可以有效地计算。如果您愿意，您可以使用结果向量 b (A|b) 来扩充矩阵 A，并将 A 置于缩减的行梯形形式以获得结果。

于 2012-01-30T20:28:36.347 回答
2

从第一列开始。您知道顶部和底部值（来自红色和黄色列表的第一个值）。从绿色列表中的第一个减去这两个的总和，现在您也有了中间值。

现在只需向右工作。

从红色列表中的下一个值中减去第一列的中间值，得到第二列的最高值。从黄色列表中的下一个值中减去相同的中间值，您将得到第二列的底部值。从绿色列表中的下一个值中减去这两者的总和，现在您就有了第二列的中间值。

等等

如果您要对此进行编码，您可以看到前两列是一种特殊情况，这会使代码变得丑陋。我建议在左侧使用两个全为零的“幽灵”列，以便您可以使用一种方法来确定每列的顶部、底部和中间值。

这也很容易推广。您只需要使用 (#rows)-1 幽灵列。

享受。

于 2012-01-29T03:43:25.730 回答
1

对于 10x15 个 1 和 0 的数组，如果忽略值限制为 1 或 0，您将尝试找到 150 个未知数并具有 10+15+2*(10+15-1) = 73 个方程。显然，您不能在此基础上创建具有独特解决方案的线性系统。

那么这个约束是否足以给出一个独特的解决方案？

对于具有以下总和的 4x4 矩阵，有两种解决方案：

- 1 1 1 1
| 1 1 1 1
\ 0 1 1 0 1 1 0
/ 0 1 1 0 1 1 0

0   0   1   0 
1   0   0   0 
0   0   0   1 
0   1   0   0 

0   1   0   0 
0   0   0   1 
1   0   0   0 
0   0   1   0

所以我不希望对更大的矩阵有一个独特的解决方案——许多地方都会存在相同的对称性：

- 1 1 0 0 1 1
| 1 1 0 0 1 1
\ 0 1 0 0 1 0 1 0 0 1 0
/ 0 1 0 0 1 0 1 0 0 1 0

0   0   0   0   1   0 
1   0   0   0   0   0 
0   0   0   0   0   0 
0   0   0   0   0   0 
0   0   0   0   0   1 
0   1   0   0   0   0 

0   1   0   0   0   0 
0   0   0   0   0   1 
0   0   0   0   0   0 
0   0   0   0   0   0 
1   0   0   0   0   0 
0   0   0   0   1   0
于 2012-01-31T23:13:01.930 回答
0

这个作为另一种变化怎么样

Count the amount of unknown squares each sum passes through   
While there are unsolved cells
   Solve all the cells which are passed through by a sum with only one unknown square
       Cells are solved by simply subtracting off all the known cells from the sum
   Update the amount of unknown squares each sum passes through

没有边界情况，但与前面的答案非常相似。这将首先解决所有角落，然后是那些与角落相邻的角落，然后是那些更靠近角落的角落，依此类推......

编辑：还将所有总和为零的路径归零，这应该解决任何可解决的问题（我认为）

于 2012-01-30T18:26:22.583 回答