title: An exact algorithm for optimal MAE stack filter design.
abstract: We propose a new algorithm for optimal MAE stack filter design. It is based on three main ingredients. First, we show that the dual of the integer programming formulation of the filter design problem is a minimum cost network flow problem. Next, we present a decomposition principle that can be used to break this dual problem into smaller subproblems. Finally, we propose a specialization of the network Simplex algorithm based on column generation to solve these smaller subproblems. Using our method, we were able to efficiently solve instances of the filter problem with window size up to 25 pixels. To the best of our knowledge, this is the largest dimension for which this problem was ever solved exactly.
authors.affiliation: Computer Science Department of the Institute of Mathematics and Statistics, University of São Paulo, Brazil. ddj@ime.usp.br
authors.forename: Domingos
authors.initials: D
authors.lastname: Dellamonica
authors.forename: Paulo J S
authors.initials: PJ
authors.lastname: Silva
authors.forename: Carlos
authors.initials: C
authors.lastname: Humes
authors.forename: Nina S T
authors.initials: NS
authors.lastname: Hirata
authors.forename: Junior
authors.initials: J
authors.lastname: Barrera
mesh_terms: D000465:Algorithms; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D012815:Signal Processing, Computer-Assisted