The pyramid match kernel: discriminative classification with sets of image features
The pyramid match kernel: discriminative classification with sets of image features
复制标题
DOI：
10.1109/iccv.2005.239
复制
发表时间：
2005-10
期刊：
影响因子：
--
通讯作者：
K. Grauman;Trevor Darrell
中科院分区：
文献类型：
--
作者：
K. Grauman;Trevor Darrell
当示例是一组特征，并且集合的基数不同且缺乏任何有意义的排序时，判别学习是具有挑战性的。基于核的分类方法可以学习复杂的决策边界，但是无序输入集上的核必须以某种方式解决对应关系，这通常是一个计算成本很高的任务，对于大的集大小来说是不切实际的。提出了一种新的快速核函数，该函数将无序特征集映射到多分辨率直方图上，并在该空间中计算加权直方图交集。这种“金字塔匹配”计算在特征数量上是线性的，并且它基于匹配对首次出现的最佳分辨率直方图单元隐式地找到对应关系。由于内核不会惩罚额外特性的存在，因此它对杂乱具有鲁棒性。我们证明了核函数是正定的，使其有效地用于学习算法，其最优解仅对Mercer核保证。我们在目标识别任务上展示了我们的算法，并表明它比目前的方法准确且速度快得多
Discriminative learning is challenging when examples are sets of features, and the sets vary in cardinality and lack any sort of meaningful ordering. Kernel-based classification methods can learn complex decision boundaries, but a kernel over unordered set inputs must somehow solve for correspondences epsivnerally a computationally expensive task that becomes impractical for large set sizes. We present a new fast kernel function which maps unordered feature sets to multi-resolution histograms and computes a weighted histogram intersection in this space. This "pyramid match" computation is linear in the number of features, and it implicitly finds correspondences based on the finest resolution histogram cell where a matched pair first appears. Since the kernel does not penalize the presence of extra features, it is robust to clutter. We show the kernel function is positive-definite, making it valid for use in learning algorithms whose optimal solutions are guaranteed only for Mercer kernels. We demonstrate our algorithm on object recognition tasks and show it to be accurate and dramatically faster than current approaches