Algorytm podziału rozmiaru na dwa przebiegi

Question

Napisałem poniższy algorytm zmiany rozmiaru, który może poprawnie skalować obraz w górę lub w dół. Jest jednak zbyt powolny ze względu na wewnętrzną iterację poprzez szereg wag w każdej pętli.

Jestem prawie pewien, że powinienem móc podzielić algorytm na dwa przebiegi, podobnie jak w przypadku dwuprzebiegowego rozmycia Gaussa, które znacznie zmniejszyłoby złożoność operacyjną i przyspieszyło działanie. Niestety nie mogę go uruchomić. Czy ktoś mógłby pomóc?

Parallel.For(
    startY, 
    endY, 
    y => 
    { 
     if (y >= targetY && y < targetBottom) 
     { 
      Weight[] verticalValues = this.verticalWeights[y].Values; 

      for (int x = startX; x < endX; x++) 
      { 
       Weight[] horizontalValues = this.horizontalWeights[x].Values; 

       // Destination color components 
       Color destination = new Color(); 

       // This is where there is too much operation complexity. 
       foreach (Weight yw in verticalValues) 
       { 
        int originY = yw.Index; 

        foreach (Weight xw in horizontalValues) 
        { 
         int originX = xw.Index; 
         Color sourceColor = Color.Expand(source[originX, originY]); 
         float weight = yw.Value * xw.Value; 
         destination += sourceColor * weight; 
        } 
       } 

       destination = Color.Compress(destination); 
       target[x, y] = destination; 
      } 
     } 
    }); 

Masy i wskaźniki obliczane są w następujący sposób. Jeden dla każdego wymiaru:

/// <summary> 
/// Computes the weights to apply at each pixel when resizing. 
/// </summary> 
/// <param name="destinationSize">The destination section size.</param> 
/// <param name="sourceSize">The source section size.</param> 
/// <returns> 
/// The <see cref="T:Weights[]"/>. 
/// </returns> 
private Weights[] PrecomputeWeights(int destinationSize, int sourceSize) 
{ 
    IResampler sampler = this.Sampler; 
    float ratio = sourceSize/(float)destinationSize; 
    float scale = ratio; 

    // When shrinking, broaden the effective kernel support so that we still 
    // visit every source pixel. 
    if (scale < 1) 
    { 
     scale = 1; 
    } 

    float scaledRadius = (float)Math.Ceiling(scale * sampler.Radius); 
    Weights[] result = new Weights[destinationSize]; 

    // Make the weights slices, one source for each column or row. 
    Parallel.For(
     0, 
     destinationSize, 
     i => 
      { 
       float center = ((i + .5f) * ratio) - 0.5f; 
       int start = (int)Math.Ceiling(center - scaledRadius); 

       if (start < 0) 
       { 
        start = 0; 
       } 

       int end = (int)Math.Floor(center + scaledRadius); 

       if (end > sourceSize) 
       { 
        end = sourceSize; 

        if (end < start) 
        { 
         end = start; 
        } 
       } 

       float sum = 0; 
       result[i] = new Weights(); 

       List<Weight> builder = new List<Weight>(); 
       for (int a = start; a < end; a++) 
       { 
        float w = sampler.GetValue((a - center)/scale); 

        if (w < 0 || w > 0) 
        { 
         sum += w; 
         builder.Add(new Weight(a, w)); 
        } 
       } 

       // Normalise the values 
       if (sum > 0 || sum < 0) 
       { 
        builder.ForEach(w => w.Value /= sum); 
       } 

       result[i].Values = builder.ToArray(); 
       result[i].Sum = sum; 
      }); 

    return result; 
} 

/// <summary> 
/// Represents the weight to be added to a scaled pixel. 
/// </summary> 
protected class Weight 
{ 
    /// <summary> 
    /// The pixel index. 
    /// </summary> 
    public readonly int Index; 

    /// <summary> 
    /// Initializes a new instance of the <see cref="Weight"/> class. 
    /// </summary> 
    /// <param name="index">The index.</param> 
    /// <param name="value">The value.</param> 
    public Weight(int index, float value) 
    { 
     this.Index = index; 
     this.Value = value; 
    } 

    /// <summary> 
    /// Gets or sets the result of the interpolation algorithm. 
    /// </summary> 
    public float Value { get; set; } 
} 

/// <summary> 
/// Represents a collection of weights and their sum. 
/// </summary> 
protected class Weights 
{ 
    /// <summary> 
    /// Gets or sets the values. 
    /// </summary> 
    public Weight[] Values { get; set; } 

    /// <summary> 
    /// Gets or sets the sum. 
    /// </summary> 
    public float Sum { get; set; } 
} 

Każdy IResampler dostarcza odpowiednią serię wag na podstawie danego indeksu. bimubowy resampler działa w następujący sposób.

/// <summary> 
/// The function implements the bicubic kernel algorithm W(x) as described on 
/// <see href="https://en.wikipedia.org/wiki/Bicubic_interpolation#Bicubic_convolution_algorithm">Wikipedia</see> 
/// A commonly used algorithm within imageprocessing that preserves sharpness better than triangle interpolation. 
/// </summary> 
public class BicubicResampler : IResampler 
{ 
    /// <inheritdoc/> 
    public float Radius => 2; 

    /// <inheritdoc/> 
    public float GetValue(float x) 
    { 
     // The coefficient. 
     float a = -0.5f; 

     if (x < 0) 
     { 
      x = -x; 
     } 

     float result = 0; 

     if (x <= 1) 
     { 
      result = (((1.5f * x) - 2.5f) * x * x) + 1; 
     } 
     else if (x < 2) 
     { 
      result = (((((a * x) + 2.5f) * x) - 4) * x) + 2; 
     } 

     return result; 
    } 
} 

Oto przykład obrazu skalowanego przez istniejący algorytm. Wynik jest poprawny (zauważ, że zachowano srebrzysty połysk).

oryginalny obraz

Obraz o połowę wielkości używając Bicubic Resampler.

Kod jest częścią znacznie większy library że piszę do przetwarzania obrazu, aby dodać corefx.

Answer 1

Dobrze, więc oto jak to zrobiłem.

Sztuczka polega na tym, aby najpierw zmienić rozmiar tylko szerokości obrazu, zachowując wysokość identyczną z oryginalnym obrazem. Przechowujemy wypadkowe piksele w tymczasowym obrazie.

To jest przypadek zmiany rozmiaru tego obrazu na nasz ostateczny wynik.

Jak widać, nie wykonujemy już iteracji w obu kolekcjach wag w każdym pikselu. Pomimo dwukrotnej iteracji zewnętrznej pętli pikselowej, algorytm był znacznie szybszy w swojej pracy, średnio o 25% szybciej na moich testowych obrazach.

// Interpolate the image using the calculated weights. 
// First process the columns. 
Parallel.For(
    0, 
    sourceBottom, 
    y => 
    { 
     for (int x = startX; x < endX; x++) 
     { 
      Weight[] horizontalValues = this.HorizontalWeights[x].Values; 

      // Destination color components 
      Color destination = new Color(); 

      foreach (Weight xw in horizontalValues) 
      { 
       int originX = xw.Index; 
       Color sourceColor = Color.Expand(source[originX, y]); 
       destination += sourceColor * xw.Value; 
      } 

      destination = Color.Compress(destination); 
      this.firstPass[x, y] = destination; 
     } 
    }); 

// Now process the rows. 
Parallel.For(
    startY, 
    endY, 
    y => 
    { 
     if (y >= targetY && y < targetBottom) 
     { 
      Weight[] verticalValues = this.VerticalWeights[y].Values; 

      for (int x = startX; x < endX; x++) 
      { 
       // Destination color components 
       Color destination = new Color(); 

       foreach (Weight yw in verticalValues) 
       { 
        int originY = yw.Index; 
        int originX = x; 
        Color sourceColor = Color.Expand(this.firstPass[originX, originY]); 
        destination += sourceColor * yw.Value; 
       } 

       destination = Color.Compress(destination); 
       target[x, y] = destination; 
      } 
     } 
    }); 

Answer 2

Możesz wypróbować ważony diagram voronoi. Spróbuj losowo zestaw punktów i oblicz wykres voronoi. Wygładź wielokąty za pomocą algorytmu Lloyda i interpoluj kolor wielokąta. Z wagą obliczyć ważony diagram voronoi. Na przykład voronoi stippling i mozaika: http://www.mrl.nyu.edu/~ajsecord/stipples.html i http://www.evilmadscientist.com/2012/stipplegen-weighted-voronoi-stippling-and-tsp-paths-in-processing/.

Answer 3

Sądząc po abstrakcyjnym punkcie widzenia (niewiele wiadomo o manipulowaniu obrazem) Wydaje mi się, że kilka razy oblicza się wartości dla wagi i sourcecolor (w najgłębszej pętli foreach) (za każdym razem, gdy ta sama para indeksów ponownie się podnosi); czy byłoby to możliwe z wyprzedzeniem je wstępnie z góry oszacować? Należy obliczyć macierz "bezpośredniego produktu" dla macierzy HorizontalWeight i VerticalWeight (po prostu mnożąc wartości dla każdej pary indeksów (x, y)), a także z wyprzedzeniem zastosować Color.Expand do źródła. Te zadania można wykonywać równolegle, a "bezpośredni produkt" (przepraszam, nie znam poprawnej nazwy dla tej bestii) powinien być dostępny w wielu bibliotekach.