Random Sets pp 97-104 | Cite as

On Optimal Filtering of Morphologically Smooth Discrete Random Sets and Related Open Problems

  • Nikolaos D. Sidiropoulos
Part of the The IMA Volumes in Mathematics and its Applications book series (IMA, volume 97)


Recently, it has been shown that morphological openings and closings can be viewed as consistent MAP estimators of (morphologically) smooth random sets immersed in clutter, or suffering from random dropouts [1][3]. These results hold for one-sided (union or intersection) noise. In the case of two-sided (union and intersection) noise we now know that this is no longer the case: in this more general setting, as it turns out, optimal estimators are not increasing operators [4]. Then, how may one efficiently compute an optimal random set estimate in this more general setting? For 1-D and certain restricted 2-D random set models the answer is provided by the Viterbi algorithm [5]. In the general case of 2-D random set models in two-sided noise the answer is unknown, and the task of finding it constitutes a challenging research problem.

Key words

Random Sets Morphological Filtering Opening Closing Dynamic Programming Viterbi Algorithm 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [1]
    N.D. Sidiropoulos, J.S. Baras, and C.A. BerensteinOptimal Filtering of Digital Binary Images Corrupted by Union/Intersection NoiseIEEE Trans. Image Processing, vol. 3, pp. 382–403, 1994.CrossRefGoogle Scholar
  2. [2]
    N.D. Sidiropoulos, D. Meleas, and T. StragasMAP Signal Estimation in Noisy Sequences of Morphologically Smooth ImagesIEEE Trans Image Processing, vol. 5, pp. 1088–1093, 1996.CrossRefGoogle Scholar
  3. [3]
    N.D. Sidiropoulos, J.S. Baras, and C.A. BerensteinFurther results on MAP Optimality and Strong Consistency of certain classes of Morphological FiltersIEEE Trans. Image Processing, vol. 5, pp. 762–764, 1996.CrossRefGoogle Scholar
  4. [4]
    N.D. SidiropoulosThe Viterbi Optimal Runlength-Constrained Approximation Nonlinear Filterin Mathematical Morphology and its Applications to Image and Signal Processing, P. Maragos, R.W. Schafer, M. Akmal Butt (Eds), pp. 195–202, Kluwer, Boston, Massachusetts, 1996.CrossRefGoogle Scholar
  5. [5]
    N.D. SidiropoulosThe Viterbi Optimal Runlength-Constrained Approximation Nonlinear FilterIEEE Trans. Signal Processing, vol. 44, pp. 586–598, 1996.CrossRefGoogle Scholar
  6. [6]
    G. ChoquetTheory of capacitiesAnn. Institute Fourier, vol. 5, pp. 131–295, 1953.MathSciNetCrossRefGoogle Scholar
  7. [7]
    D.G. KendallFoundations of a theory of random setsin Stochastic Geometry, E.F. Harding and D.G. Kendall, Eds., pp. 322–376. John Wiley, London, England, 1974.Google Scholar
  8. [8]
    G. MatheronElements pour une theorie des Milieux PoreuxMasson, 1967.Google Scholar
  9. [9]
    G. MatheronRandom Sets and Integral GeometryWiley, New York, 1975.zbMATHGoogle Scholar
  10. [10]
    K. Sivakumar and J. GoutsiasBinary Random Fields Random Closed Sets and Morphological SamplingIEEE Trans. Image Processing, vol. 5, pp. 899–912, 1996.CrossRefGoogle Scholar
  11. [11]
    L. WEISNERAbstract theory of inversion of finite seriesTrans. AMS, vol. 38, pp. 474–484, 1935.MathSciNetCrossRefGoogle Scholar
  12. [12]
    M. WardThe algebra of lattice functionsDuke Math. J., vol. 5, pp. 357–371, 1939.MathSciNetzbMATHCrossRefGoogle Scholar
  13. [13]
    Gian-Carlo RotaOn the Foundations of Combinatorial Theory: I. Theory of Moebius FunctionsZ. Wahrscheinlichkeitstheorie und Verw. Gebiete, vol. 2, pp. 340–368, 1964. Also appears in Classic Papers in Combinatorics, I. Gessel and G-C. Rota (Eds.), Birkhauser, Boston,1987.MathSciNetzbMATHCrossRefGoogle Scholar
  14. [14]
    H.H. CrapoMoebius Inversion in LatticesArch. Math., vol. 19, pp. 595–607, 1968. Also appears in Classic Papers in Combinatorics, I. Gessel and G-C. Rota (Eds.), Birkhauser, Boston,1987.MathSciNetCrossRefGoogle Scholar
  15. [15]
    M. AignerCombinatorial TheorySpringer-Verlag, New York, 1979.zbMATHCrossRefGoogle Scholar
  16. [16]
    H. Mathis ThomaBelief function computationsin Conditional Logic in Expert Systems, I.R. Goodman, M.M Gupta, H.T. Nguyen, and G.S. Rogers, Eds. 1991, pp. 269–308, Elsevier Science Publishers B.V. (North Holland).Google Scholar
  17. [17]
    J. SerraImage Analysis and Mathematical MorphologyAcademic Press, New York, 1982.zbMATHGoogle Scholar
  18. [18]
    J. SerraImage Analysis and Mathematical Morphology vol. 2 Theoretical AdvancesAcademic Press, San Diego, 1988.zbMATHGoogle Scholar
  19. [19]
    H.J.A.M. HeijmansMorphological Image OperatorsAcademic Press, Boston, 1994.zbMATHGoogle Scholar
  20. [20]
    E.R. DoughertyOptimal Mean Square N-Observation Digital Morphological Filters - I. Optimal Binary FiltersComputer Vision, Graphics, and Image Processing: Image Understanding, vol. 55, pp. 36–54, 1992.Google Scholar
  21. [21]
    R.M. Haralick, E.R. Dougherty, and P.L. KatzModel-based morphologyin Proc. SPIE, Vol. 1472, Orlando, Florida. Society for Optical Engineering, April 1991.Google Scholar
  22. [22]
    E.R. Dougherty, A. Mathew, and V. SwarnakarA conditional-expectationbased implementation of the optimal mean-square binary morphological filterin Proc. SPIE, Vol. 1451, San Jose, California. Society for Optical Engineering, February 1991.Google Scholar
  23. [23]
    E.R. Dougherty, ed.Mathematical Morphology in Image ProcessingMarcel Dekker, New York, 1993.Google Scholar
  24. [24]
    E.R. DoughertyOptimal mean-absolute-error filtering of gray-scale signals by the morphological hit-or-miss transformJournal of Mathematical Imaging and Vision, vol. 4, pp. 255–271, 1994.MathSciNetCrossRefGoogle Scholar
  25. [25]
    E.R. Dougherty, J. Newell, and J. PelzMorphological texture-based maximum-likelihood pixel classification based on local granulometric momentsPattern Recognition, vol. 25, pp. 1181–1198, 1992.CrossRefGoogle Scholar
  26. [26]
    D. Schonfeld and J. GoutsiasOptimal morphological pattern restoration from noisy binary imagesIEEE Transactions on Pattern Anal. Mach. Intell., vol. 13, pp. 14–29, 1991.CrossRefGoogle Scholar
  27. [27]
    D. SchonfeldOptimal Structuring Elements for the Morphological Pattern Restoration of Binary ImagesIEEE Transactions on Pattern Anal. Mach. Intell., vol. 16, pp. 589–601, 1994.CrossRefGoogle Scholar
  28. [28]
    D. Schonfeld and J. GoutsiasOn the morphological representation of binary images in a noisy environmentJournal of Visual Communication and Image Representation, vol. 2, pp. 17–30, 1991.CrossRefGoogle Scholar
  29. [29]
    J. GoutsiasMorphological Analysis of Discrete Random ShapesJournal of Mathematical Imaging and Vision, vol. 2, pp. 193–215, 1992.MathSciNetzbMATHCrossRefGoogle Scholar
  30. [30]
    N.D. Sidiropoulos, J.S. Baras, and C.A. BerensteinAn Algebraic Analysis of the Generating Functional for Discrete Random Sets and Statistical Inference for Intensity in the Discrete Boolean Random Set ModelJournal of Mathematical Imaging and Vision, vol. 4, pp. 273–290, 1994.CrossRefGoogle Scholar
  31. [31]
    A.J. ViterbiError bounds for convolutional codes and an asymptotically optimum decoding algorithmIEEE Trans. Information Theory, vol. 13, pp. 260–269, 1967.zbMATHCrossRefGoogle Scholar
  32. [32]
    J.K. OmuraOn the Viterbi decoding algorithmIEEE Trans. Information Theory, vol. 15, pp. 177–179, 1969.MathSciNetCrossRefGoogle Scholar
  33. [33]
    R. BellmanDynamic ProgrammingPrinceton University Press, Princeton, N.J., 1957.zbMATHGoogle Scholar
  34. [34]
    R. Bellman and S. DreyfusApplied Dynamic ProgrammingPrinceton University Press, Princeton, N.J., 1962.zbMATHGoogle Scholar
  35. [35]
    A. Blake and A. ZissermanVisual ReconstructionMIT Press, Cambridge, Mass., 1987.Google Scholar
  36. [36]
    S. Geman and D. GemanStochastic relaxation Gibbs distributions and the Bayesian restoration of imagesIEEE Trans. PAMI, vol. 6, pp. 721–741, 1984.zbMATHCrossRefGoogle Scholar
  37. [37]
    G.L. Bibro, W.E. Snyder, S.J. Garnier, and J.W. GaultMean field annealing: A formalism for constructing GNC-Like algorithmsIEEE Trans. Neural Networks, vol. 3, pp. 131–138, 1992.CrossRefGoogle Scholar
  38. [38]
    D. Geman, S. Geman, C. Graffigne, and P. DongBoundary detection by constrained optimizationIEEE Trans. PAMI, vol. 12, pp. 609–627, 1990.CrossRefGoogle Scholar
  39. [39]
    D. Geman and C. YangNonlinear image recovery with half-quadratic regularizationIEEE Trans. Image Processing, vol. 4, pp. 932–946, 1995.CrossRefGoogle Scholar

Copyright information

© Springer Science+Business Media New York 1997

Authors and Affiliations

  • Nikolaos D. Sidiropoulos
    • 1
  1. 1.Department of Electrical EngineeringUniversity of VirginiaCharlottesvilleUSA

Personalised recommendations