Abstract
Image segmentation can be a useful tool in facing image degradation. In image segmentation the input is a set of pixels with given grey levels and the output is a partition of the set of pixels into connected regions ("classes"), so that a given set of requirements on the single classes and on adjacent classes is satisfied (i.e. pixels belonging to the same class must have approximately the same grey levels or the same textures and pixels belonging to adjacent classes must have significantly different grey levels or different textures). Once segmentation has been performed, the same grey level is associated with each pixel of the same class. The grey level can either be related to the original grey levels of the class, or can be given by a new grey scale on the ground of contrast optimization criteria. The segmentation technique proposed in this presentation is a method for finding the most homogeneous classes and the best possible contrast in a row by row image processing. In partitioning each row of the image, we have two aims: the partition must be as good as possible in its own right, and it must be as compatible as possible with the partitions of the other rows. If we take into account the two aims simultaneously, then the solution procedure becomes complex. To simplify and speed-up the procedure, we can partition each row independently, and then we can apply region merging techniques to the resulting set of row partitions. In the presentation the problem is formulated as a path partitioning one and a simple O(n p) row-partitioning algorithm based on a shortest path formulation of the problem is given.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aparo E.L., Simeone B.: Equipartizione di un grafo: un'applicazione all'informatica medica. Applicazioni del calcolo (I. Galligani ed.), CNR, Rome, pp.77–86, 1975.
Agasi E., Becker R.I., Perl Y.: A shifting algorithm for min-max constraint partition on trees. Proc. 16-th Conf. on Information Science and Systems, Princeton, 1982.
Ballard D.H., Brown C.M.: Computer vision. Prentice Hall, 1982.
Becker R.I., Perl Y., Schach S.R.: A shifting algorithm for min-max tree partitioning. J.ACM 29, pp.58–67, 1982.
Becker R.I., Perl Y.: Shifting algorithms for tree partitioning with general weighting functions. J. Algorthms 4, pp.101–120, 1983.
Camerini P.M.: The min-max spanning tree problem and some extensions. Inf. Proc. Letters, 7 pp. 10–14, 1978.
Coggins J.M., Jain A.K.: A spatial filtering approach to texture analysis. Pattern Recognition Letters 3, pp.195–203, 1985.
Coleman G.B., Andrews H.C.: Image segmentation by clustering. Proc. IEEE 67, pp.773–785, 1979.
De Simone C., Lucertini M., Pallottino S., Simeone B.: Fair dissections of spiders, worms and caterpillars. EURO VII, Bologna, 1985 (also RUTCOR RRR 17–86, Rutgers Univ., 1986). To appear on NETWORKS.
Fulkerson D.R.: Flow networks and combinatorial Operations Research. In: A.M. Geoffrion (Ed.): Perspectives on optimization. Addison Wesley, Reading Mass., 1972.
Garey M.R., Johnson D.S.: Computers and intractability. Freeman, San Francisco (Cal), 1979.
Gonzales R.C., Wintz P.: Digital image processing. Addison-Wesley, Reading (Mass.), 1977.
Hoffman R., Jain A.K.: Segmentation and classification of range images. IEEE Tr. on Pattern Analysis and Machine Intelligence, 9, pp.608–620, 1987.
Hord R.M.: Digital Image Processing of Remotely Sensed Data. Academic Press, New York, 1982.
Jain A.K.: Experiments in texture analysis using spatial filtering. Proc. IEEE workshop on Languages for Automation, Palme de Mallorca, June, pp.66–70, 1985.
Jain A.K., Dubes R.C.: Algorithms for clustering data. Prentice Hall, 1988.
Kundu S., Misra J.: A linear tree-partitioning algorithm. SIAM J. Computing 6, pp.131–134, 1977.
Lucertini M., Perl Y., Simeone B.: Most uniform partitioning and its use in image processing. In preparation.
Mitchell O.R., Carlton S.C.: Image segmentation using a local extrema texture measure. Pattern Recognition, 10, pp.205–210, 1978.
Pavlidis T.: Structural pattern recognition. Springer, New York, 1977.
Perl Y., Schach S.R.: Max-min tree-partitioning. J. ACM 28, n.1, pp.5–15, 1981.
Perl Y., Snir M.: Circuit partitioning with size and connection constraints. NETWORKS 13, pp.365–375, 1983.
Perl Y., Vishkin U.: Efficient implementation of a shifting algorithm. Discrete Applied Math. 12, pp.71–80, 1985.
Rosenfeld A., Kak A.C.: Digital picture processing (2 volumes). Academic Press, New York, 1982.
Schachter B.J., Davis L.S., Rosenfeld A.: Some experiments in image segmentation by clustering of local feature values. Pattern Recognition, 11, pp.19–28, 1978.
Young T.Y., Fu K.S.: Handbook of Pattern Recognition and Image Processing. Academic Press, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Lucertini, M., Perl, Y., Simeone, B. (1989). Image enhancement by path partitioning. In: Cantoni, V., Creutzburg, R., Levialdi, S., Wolf, G. (eds) Recent Issues in Pattern Analysis and Recognition. Lecture Notes in Computer Science, vol 399. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51815-0_37
Download citation
DOI: https://doi.org/10.1007/3-540-51815-0_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51815-0
Online ISBN: 978-3-540-46815-8
eBook Packages: Springer Book Archive