Advanced search
Start date

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


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)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items