Hu Weiming, Wu Baoxin, Wang Pei, Yuan Chunfeng, Li Yangxi, Maybank Stephen
IEEE Trans Image Process. 2018 Jun 22. doi: 10.1109/TIP.2018.2849885.
Graphs are effective tools for modeling complex data. Setting out from two basic substructures, random walks and trees, we propose a new family of context-dependent random walk graph kernels and a new family of tree pattern graph matching kernels. In our context-dependent graph kernels, context information is incorporated into primary random walk groups. A multiple kernel learning algorithm with a proposed l1,2-norm regularization is applied to combine context-dependent graph kernels of different orders. This improves the similarity measurement between graphs. In our tree-pattern graph matching kernel, a quadratic optimization with a sparse constraint is proposed to select the correctly matched tree-pattern groups. This augments the discriminative power of the tree-pattern graph matching. We apply the proposed kernels to human action recognition, where each action is represented by two graphs which record the spatiotemporal relations between local feature vectors. Experimental comparisons with state-of-the-art algorithms on several benchmark datasets demonstrate the effectiveness of the proposed kernels for recognizing human actions. It is shown that our kernel based on tree-pattern groups, which have more complex structures and exploit more local topologies of graphs than random walks, yields more accurate results but requires more runtime than the context-dependent walk graph kernel.
图是对复杂数据进行建模的有效工具。从两个基本子结构——随机游走和树出发，我们提出了一类新的上下文相关随机游走图核以及一类新的树模式图匹配核。在我们的上下文相关图核中，上下文信息被纳入到主要的随机游走组中。一种采用所提出的l1,2范数正则化的多核学习算法被用于组合不同阶的上下文相关图核。这提高了图之间的相似性度量。在我们的树模式图匹配核中，提出了一种带有稀疏约束的二次优化方法来选择正确匹配的树模式组。这增强了树模式图匹配的判别能力。我们将所提出的核应用于人类动作识别，其中每个动作由两个记录局部特征向量之间时空关系的图来表示。在几个基准数据集上与现有算法进行的实验比较证明了所提出的核在识别人类动作方面的有效性。结果表明，我们基于树模式组的核，其结构比随机游走更复杂且利用了图的更多局部拓扑结构，能产生更准确的结果，但比上下文相关游走图核需要更多的运行时间。
