TY - JOUR

T1 - Most uniform path partitioning and its use in image processing

AU - Lucertini, Mario

AU - Perl, Yehoshua

AU - Simeone, Bruno

N1 - Funding Information:
We thank Professors Rainer Schrader and Jarik NeSetIil for their useful comments. The financial support from the “Minister0 della Pubblica Istruzione”, Italy, is gratefully acknowledged. Sectionso f this paper were written while the seconda uthor was visiting the De-

PY - 1993/4/27

Y1 - 1993/4/27

N2 - Let Q be a vertex-weighted path with n vertices. For any pair (L,U) can one find a partition of Q into (a given number p of) subpaths, such that the total weight of every subpath lies between L and U? We present linear-time algorithms for the partitioning problem for given (L,U) and an O(n2 p log n) algorithm, relying on the above procedures, for finding a partition that minimizes the difference between the largest and the smallest weight of a subpath (most uniform partitioning). Our approach combines a preprocessing procedure, which detects "obstructions", if any, via a sequence of vertex compressions; and a greedy procedure, which actually finds the desired partition. Path partitioning can be a useful tool in facing image degradation. In fact whenever a picture is taken or converted from one form to another, the resulting image can be affected by different types and degrees of degradation; if we have no informations on the actual degradation process that has taken place on the image (or if it is too difficult or costly to find such informations), the only way for image enhancement consists in increasing contrast and reducing noise by suitable modifications of the grey level of pixels. Finding the optimal grey scale transformation which leads to this enhancement can be formulated as the problem of partitioning into connected components a path with vertices corresponding to grey levels and vertex weights equal to the number of occurrences of the corresponding tone in the image, so that the sum of the weights of the vertices in each component is "as constant as possible". In addition to image processing, this problem has applications in paging, clustering and the design of communication networks.

AB - Let Q be a vertex-weighted path with n vertices. For any pair (L,U) can one find a partition of Q into (a given number p of) subpaths, such that the total weight of every subpath lies between L and U? We present linear-time algorithms for the partitioning problem for given (L,U) and an O(n2 p log n) algorithm, relying on the above procedures, for finding a partition that minimizes the difference between the largest and the smallest weight of a subpath (most uniform partitioning). Our approach combines a preprocessing procedure, which detects "obstructions", if any, via a sequence of vertex compressions; and a greedy procedure, which actually finds the desired partition. Path partitioning can be a useful tool in facing image degradation. In fact whenever a picture is taken or converted from one form to another, the resulting image can be affected by different types and degrees of degradation; if we have no informations on the actual degradation process that has taken place on the image (or if it is too difficult or costly to find such informations), the only way for image enhancement consists in increasing contrast and reducing noise by suitable modifications of the grey level of pixels. Finding the optimal grey scale transformation which leads to this enhancement can be formulated as the problem of partitioning into connected components a path with vertices corresponding to grey levels and vertex weights equal to the number of occurrences of the corresponding tone in the image, so that the sum of the weights of the vertices in each component is "as constant as possible". In addition to image processing, this problem has applications in paging, clustering and the design of communication networks.

UR - http://www.scopus.com/inward/record.url?scp=38249002289&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249002289&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(93)90048-S

DO - 10.1016/0166-218X(93)90048-S

M3 - Article

AN - SCOPUS:38249002289

SN - 0166-218X

VL - 42

SP - 227

EP - 256

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2-3

ER -