13、SIFTpack：高效SIFT匹配的紧凑表示

SIFTpack：高效SIFT匹配的紧凑表示

1. 高效匹配解决方案

在图像分析和处理中，SIFT（尺度不变特征变换）描述符常被用于特征提取。为了更高效地存储和处理这些描述符，我们提出了SIFTpack。SIFTpack不仅能节省存储空间，更重要的是能显著减少计算时间。其主要优势在于可将其视为一个8层图像，从而能运用现有的图像匹配算法。

2. 计算所有距离

在图像分割、共分割和自相似性估计等应用中，需要计算给定集合内或两个集合间所有（或多个）SIFT描述符对之间的距离。当描述符数量较多时，简单计算所有距离的时间复杂度为$O(M^2)$，其中$M$是描述符的数量。

将描述符存储在SIFTpack中可以避免冗余计算，从而实现更高效的计算。以下是高效计算所有距离的算法：

Algorithm 3 All distances between SIFTs Input: SIFTpacks S1 and S2 for all shifts k, l do – Compute the element-wise square difference = (S1 - S2[k,l])^2 – Compute the Integral Image F(), summing the 8 layers. – The distance between S1i;j and S2k;l i;j is equal to: F(i, j) + F(i + 3, j + 3) - F(i + 3, j) - F(i, j + 3) end for Output: Di