On the tractability of estimating the germ process of certain germ–grain random set models and related problems

摘要

The germ process embedded in a germ–grain random set is often not merely part of a constructive mathematical model, but has physical significance as well, e.g., in the modeling of cell cultures. In such situations, knowledge of the realization of the germ process associated with a particular random set observation is highly desirable. In this paper, it is shown that, for an interesting class of germ–grain models, maximum likelihood estimation of the germ process on the basis of a random set observation is an NP-complete computational problem. Certain additional computational problems associated with the probabilistic specification of morphologically processed random sets are also discussed.