ON INTEGER PROGRAMMING APPROACHES FOR MORPHOLOGICAL TEMPLATE DECOMPOSITION PROBLEMS IN COMPUTER VISION

In morphological image processing and analysis, a template or structur ing element is applied to an image. Often savings in computation time and a better fit to the given computer architecture can be achieved by using the technique of template decomposition. Researchers have writt en a multitude of papers on finding such decompositions for special cl asses of templates. Justifying recent integer programming approaches t o the morphological template decomposition problem in its general form , this paper proves the NP-completeness of this problem.