Most uniform path partitioning and its use in image processing (Q1803677): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: A shifting algorithm for constrained min-max partition on trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Shifting algorithms for tree partitioning with general weighting functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Shifting Algorithm for Min-Max Tree Partitioning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fair dissections of spiders, worms, and caterpillars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Meet-distributive lattices and the anti-exchange closure / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3883550 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4165427 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Balanced optimization problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Max-Min Tree Partitioning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Circuit partitioning with size and connection constraints / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient implementation of a shifting algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3679094 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Amortized Computational Complexity / rank
 
Normal rank

Latest revision as of 17:53, 17 May 2024

scientific article
Language Label Description Also known as
English
Most uniform path partitioning and its use in image processing
scientific article

    Statements

    Most uniform path partitioning and its use in image processing (English)
    0 references
    0 references
    0 references
    0 references
    29 June 1993
    0 references
    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 beween \(L\) and \(U\)? We present linear-time algorithms for the partitioning problem for given \((L,U)\) and an \(O(n^ 2p/\) \(\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 its 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 occurences 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.
    0 references
    0 references
    linear-time algorithms
    0 references
    partitioning problem
    0 references
    image degradation
    0 references
    image enhancement
    0 references
    grey scale transformation
    0 references