An efficient multilinear optimization framework for hypergraph matching

Quynh Nguyen, Francesco Tudisco, Gautier Antoine, Matthias Hein

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows the use of higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to state-of-the-art performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourth-order problem can be avoided yielding a third-order scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.
LanguageEnglish
Pages1054-1075
Number of pages22
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume39
Issue number6
Early online date31 May 2016
DOIs
Publication statusPublished - 1 Jun 2016

Fingerprint

Hypergraph
Fourth Order
Ascent
Optimization
Multilinear Forms
Computer vision
Optimization Problem
Correspondence Problem
Tensors
Score Function
Homotopy Type
Monotonic
Computer Vision
Assignment
Tensor
NP-complete problem
Higher Order
Framework

Keywords

  • hypergraph matching
  • tensor
  • multilinear form
  • block coordinate ascent

Cite this

Nguyen, Quynh ; Tudisco, Francesco ; Antoine, Gautier ; Hein, Matthias. / An efficient multilinear optimization framework for hypergraph matching. In: IEEE Transactions on Pattern Analysis and Machine Intelligence. 2016 ; Vol. 39, No. 6. pp. 1054-1075.
@article{5630ecce4fde464eb6a16519aae86fe9,
title = "An efficient multilinear optimization framework for hypergraph matching",
abstract = "Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows the use of higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to state-of-the-art performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourth-order problem can be avoided yielding a third-order scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.",
keywords = "hypergraph matching, tensor, multilinear form, block coordinate ascent",
author = "Quynh Nguyen and Francesco Tudisco and Gautier Antoine and Matthias Hein",
note = "(c) 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.",
year = "2016",
month = "6",
day = "1",
doi = "10.1109/TPAMI.2016.2574706",
language = "English",
volume = "39",
pages = "1054--1075",
journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
issn = "0162-8828",
number = "6",

}

An efficient multilinear optimization framework for hypergraph matching. / Nguyen, Quynh; Tudisco, Francesco; Antoine, Gautier; Hein, Matthias.

In: IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 39, No. 6, 01.06.2016, p. 1054-1075.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An efficient multilinear optimization framework for hypergraph matching

AU - Nguyen, Quynh

AU - Tudisco, Francesco

AU - Antoine, Gautier

AU - Hein, Matthias

N1 - (c) 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.

PY - 2016/6/1

Y1 - 2016/6/1

N2 - Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows the use of higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to state-of-the-art performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourth-order problem can be avoided yielding a third-order scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.

AB - Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows the use of higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to state-of-the-art performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourth-order problem can be avoided yielding a third-order scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.

KW - hypergraph matching

KW - tensor

KW - multilinear form

KW - block coordinate ascent

UR - http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=34

UR - https://arxiv.org/abs/1511.02667

U2 - 10.1109/TPAMI.2016.2574706

DO - 10.1109/TPAMI.2016.2574706

M3 - Article

VL - 39

SP - 1054

EP - 1075

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

T2 - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

SN - 0162-8828

IS - 6

ER -