Image enhancement by path partitioning

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.