Efficient algorithms for max-norm optimization in image analysis and computer vision

• Grant number: 19/08759-2
• Support type: Regular Research Grants
• Duration: October 01, 2021 - March 31, 2023
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Cooperation agreement: Uppsala University
• Mobility Program: SPRINT - Projetos de pesquisa - Mobilidade
• Principal researcher: Alexandre Xavier Falcão
• Grantee: Alexandre Xavier Falcão
• Principal researcher abroad: Filip Malmberg
• Institution abroad: Uppsala University (UU), Sweden
• Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 14/12236-1 - AnImaLS: Annotation of Images in Large Scale: what can machines and specialists learn from interaction?, AP.TEM

Abstract

This proposal is part of a larger research initiative, in which we study a specific class of optimization problems where the objective function is defined as the max-norm, over a set of variables. Such optimization problems have occurred frequently in the image processing literature (e.g., in image filtering, segmentation, and registration problems). It is well known that for many specific max-norm optimization problems, globally optimal solutions can be found using very efficient quasi-linear time algorithms. Despite the success of these methods in solving certain special cases, their limitations and potential in terms of general max-norm optimization remain unclear. Therefore, our overall long term goal is to provide a detailed and systematic characterization of the class of max-norm optimization problems that can be solved using efficient, low-order polynomial time, algorithms. In this proposal, we focus on a limited subproblem within this larger initiative. The proposal is based on a recent discovery by the applicants: a strong theoretical connection between max-norm optimization problems and the classical computer science problem of boolean satisfiability. This novel and previously unexplored connection provides a clear framework in which new and existing algorithms for solving max-norm optimization problems can be formulated and compared. As a direct consequence of this connection, we have showed that the class of max-norm problems that can be solved in polynomial time is significantly larger than what was previously known. While this proof provides a general computation strategy for solving such optimization problems, it does not directly lead to an efficient algorithm. The aim of this proposal is therefore to formulate and implement, based on our theoretical results, algorithms for solving max-norm optimization problems in image processing that are efficient, both in terms of asymptotic complexity and in practice. (AU)