Matrix decomposition in minimax algebra and applications in image processing

Minimax algebra is a mathematical theory which originated from problems in operations research and machine scheduling. Surprising parallelisms exist between linear algebra and minimax algebra. Both linear algebra and minimax algebra can be embedded into the mathematical theory of image algebra which forms a unified mathematical environment for all image processing and computer vision applications.;Methods for matrix decomposition in linear algebra have found numerous applications in image processing, in particular for the problem of template decomposition. Therefore, it seems reasonable to investigate matrix decomposition techniques in minimax algebra with applications in image processing. We provide a mathematical basis for these investigations by establishing a new theory of rank within minimax algebra. Thus far, only minimax decompositions of rank 1 matrices into outer product expansions are known to the image processing community. This dissertation derives various new methods for the decomposition of matrices of rank larger than 1 within minimax algebra.;Moreover, this thesis proves the NP-completeness of the problem of decomposing arbitrary matrices in minimax algebra. Consequently, we obtain a fundamental result for the area of morphological image processing: the NP-completeness of the general morphological template decomposition problem.