An exact algorithm for optimal MAE stack filter design.
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.
Dellamonica
Domingos
D
Computer Science Department of the Institute of Mathematics and Statistics, University of São Paulo, Brazil. ddj@ime.usp.br
Silva
Paulo J S
PJ
Humes
Carlos
C
Hirata
Nina S T
NS
Barrera
Junior
J
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