当前位置：首页 > news >正文

K-M算法（图像凭借特征点匹配）

news 2024/11/7 0:15:16

K-M算法，也被称为匈牙利算法。
二分图匹配算法，K-M也可以应用到图像拼接上的特征点匹配。
其主要利用两个可行顶标的调节以及等价子图的生成，从而加权二分图退化成无权二分图，最后利用寻求增广矩阵来求解无权二分图的最佳匹配。
先投票处理（枚举）任意可能的每对MLD特征之间的距离（汉明距离两个先行描述符进行异或中1的个数）

//时间复杂度为O(n^3) 
#include <bits/stdc++.h>
using namespace std;
const in N = 1e4 + 10;
//N待定
vector<int> MLD1[N], MLD2[N];
//二分图所以要分开存储两组MLD特征 计算两组MLD之间的汉明距离
int w[N][N]; 
int tsd;
//upd[j] 表示与右部节点 j 匹配的所有左部节点 i 中，la[i] + lb[j] - w[i][j] 的最小值
int upd[N];
bool ast[N], bst[N]; //记录左、右部节点是否在交错树中
int match[N]; //记录每个右部节点匹配了哪一个左部节点
int last[N]; //记录每个右部节点的最小upd值对应的左部节点
int find(int x, int fa) {ast[u] = 1;for (int i = 0; i < N2; i ++ ){if (!bst[i]){if (la[u] + lb[i] == w[u][i]){bst[i] = 1;last[i] = u;//?if (match[i] == 0 || find(match[i], i)){//判断是否匹配对象或者用find函数递归找到匹配对象的增广路径并更新match[i] = u;return 1;}}else if (upd[i] > la[u] + lb[i] - w[u][i]){upd[i] = la[u] + lb[i] - w[u][i];last[i] = u;}}}return 0;
} void km(){for (int i = 0; i < N1; i ++){lx[i] = max(lx[i], w[i][j]);}memset(ly, -1, sizeof ly);for (int i = 0; i < N1; i ++ ){//为所有左部节点进行匹配 //初始化memset(ast, 0, sizeof ast);memset(bst, 0, sizeof bst);memset(upd, 0x3f, sizeof upd);//从右部节点st匹配的左节点match[st]开始匹配，一开始假设有一条0-i的匹配int st = 0;match[0] = i;while(match[st]){int minn = 0x3f3f3f3f;if (find(match[st], st)) break;//匹配失败修改顶标，在这之前需要找出最小的upd值 for (int j = 0; j < N2; j ++ ) {if((!bst[j] && minn > upd[j])){minn = upd[j];st = j;//下一次直接从最小边开始搜索} }//修改顶标for (int j = 0;j < N2; j ++ ){if(ast[j]) la[j] -= minn; //将交错树中的左部节点减去最小upd值if(bst[j]) lb[j] += minn; //将交错树中的右部节点加上最小upd值else upd[j] -= minn; //能匹配到的左部节点已经减去最小upd值，对应的upd值也需要减去最小upd值} bst[st] = 1;}while(st) //倒退更新增广路径{match[st] = match[last[st]];st = last[st];}}
}
int main()
{//输入 MLD1 MLD2 tsdfor (int i = 0;i < N1; i ++ ){for (int j = 0; j < N2; j ++ ){w[i][j] = 0;for (int d1 = 0; d1 != MLD1[i].size(); d1 ++ ) {//MLD1[i]中任一线段描述符 for (int d2 = 0; d2 != MLD2[j].size(); d2 ++ ) {//MLD2[j]中任一线段描述符 res = POPCNT(MLD1[i][d1] ^ MLD2[j][d2]);//异或后1的个数  1越少距离越近 //但是这里可以二分图最大权重匹配 所以加上了n-res if (res < tsd) w[i][j] = w[i][j] + n - res;}}}} //生成两组可行顶标lx[N1] ly[N2] 一定要保证N1<=N2//对于每一个左侧点有一个顶标lx[i],初始时为i连出边的最大值//对于每一个右侧的点也有个顶标ly[j],初始时为0//在任何时候，对于一条i连向j的边e，满足lx[i] + ly[j] >= e//定义一个原图的子图 G"，其中的边满足 lx[i]+ly[j]=we，初始状态下子图由左侧点连出的最大边构成//应该模仿匈牙利算法，在增广路上寻找（bfs），由于没有最大匹配，可能需要降低某个左侧点的标准km();for (int i = 0; i < N1; i ++ ) cout << match[i] << "\n";return 0;}

基于网格优化的图像对齐算法

对极几何约束

极几何约束的投影模型是立体视觉中的核心，涉及描述两张图像之间的几何关系，特别是如何从两张不同视角的图像推导出关于三维场景的信息。其推导过程通常从投影几何的基本概念出发，结合相机模型，最终导出极几何约束。
假设三位世界点 $P = (X,Y,Z)^{T}$ 通过相机投影到图像平面上的点 $x = (x,y,1)^{T}$
在齐次坐标下，相机投影可以通过一下公式表示： $x = K [R ∣ t] P$

K是相机的内参矩阵，包含了相机的焦距和主点位置等信息；
R是相机的旋转矩阵；
t是相机的平移向量；
$[R ∣ t]$ 形成了相机的外参矩阵
对于两个不同的视角，假设我们有两个相机 C1 和 C2 ，它们分别有相应的内参矩阵K1,K2 ，旋转矩阵 R1,R2，以及平移向量 t1,t2 。
相机C1中，点P的投影为： $x 1 = K 1 [R 1∣ t 1] P$
相机C2中，点P的投影为： $x 2 = K 2 [R 2∣ t 2] P$
对于任意一对对应的图像点x1和x2，他们必须满足：
$x2^{T}Fx1 = 0$
F为基础矩阵，基础矩阵是一个 3x3 的矩阵，它的存在确保了对应点满足极线约束。
计算基础矩阵F通过公式计算：
$F = K2^{-T}[t✖R]K1^{-1}$ (三维)

本质矩阵

本质矩阵E是描述两个相机坐标系下的对应点之间的几何关系的矩阵。它与基础矩阵类似，都满足极几何约束，但是本质矩阵适用于两个相机已知内参的情况。
$x2^{T}Ex1 = 0$
E和F之间的关系：
$E = K2^{T}FK1$
$F = K2^{-T}Ek1^{-1}$
基础矩阵描述的是图像坐标之间的关系，而本质矩阵描述的是在相机坐标系中的几何关系。

本质矩阵的秩为 2，即它的特征值中有一个为零。它是一个 3×3 的矩阵，可以表示为如下形式：
$E = [t] ✖ R$

R是相机之间的旋转矩阵
$[t] ✖$ 是平移向量t对应的反对称矩阵（3×3）
（在线性代数中，反对称矩阵（或称斜对称矩阵）指转置矩阵和自身的加法逆元相等的方形矩阵 $A^{T} = -A$ ）
本质矩阵的计算
从点对获取本质矩阵
如果我们已经知道了图像中的对应点对 {x1,x2}，可以通过八点法等方法来估计本质矩阵。通过这些方法，我们可以得到一个包含旋转和平移信息的本质矩阵。
相机标定
$E = K2^{T}FK1$

SVD分解矩阵

给定一个m*n的矩阵A，奇异值分解将其表示为三个矩阵的乘积：
$A = UΣV^{T}$

U 是一个 m×m 的正交矩阵，包含矩阵 A 的左奇异向量
Σ是一个 m×n 的对角矩阵，包含矩阵 A 的奇异值。奇异值是矩阵 A 的特征值的平方根，并且按降序排列。
$V^{T}$ 是一个 n×n 的正交矩阵，包含矩阵 A 的右奇异向量。
左奇异向量：矩阵 A 的左奇异向量是矩阵 U 中的列向量，记为 u1,u2,…,ur ，这些向量是 $A^{T}A$ 的特征向量
右奇异向量：矩阵 A 的右奇异向量是矩阵 U 中的列向量，记为 u1,u2,…,ur ，这些向量是 $AA^{T}$ 的特征向量
SVD计算：Jacobi算法、Golub-Kahan算法
现代计算软件（如 NumPy、MATLAB）通过高效的数值算法实现了 SVD 的快速计算。