src/Tizen.NUI/src/internal/Utility/ColorCutQuantizer.cs

   1 /*
   2  * Copyright (c) 2021 Samsung Electronics Co., Ltd.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  *
  16  */
  17
  18 /*
  19  * Copyright (C) 2017 The Android Open Source Project
  20  *
  21  * Modified by Woochan Lee(wc0917.lee@samsung.com)
  22  */
  23
  24 using System;
  25 using System.Collections;
  26 using System.Collections.Generic;
  27 using System.Linq;
  28
  29 namespace Tizen.NUI
  30 {
  31     internal sealed class ColorCutQuantizer
  32     {
  33         private const float blackMaxLightness = 0.05f;
  34         private const float whiteMinLightness = 0.95f;
  35         private const int componentRed = -3;
  36         private const int componentGreen = -2;
  37         private const int componentBlue = -1;
  38
  39         private static Dictionary<int, int> colorPopulations;
  40         private static int[] colors;
  41         private List<Palette.Swatch> quantizedColors;
  42         private float[] tempHsl = new float[3];
  43
  44         private ColorCutQuantizer(ColorHistogram colorHistogram, int maxColors)
  45         {
  46             if (colorHistogram == null)
  47             {
  48                 throw new ArgumentNullException(nameof(colorHistogram), "colorHistogram should not be null.");
  49             }
  50
  51             if (maxColors < 1)
  52             {
  53                 throw new ArgumentNullException(nameof(maxColors), "maxColors should not be null.");
  54             }
  55
  56             int rawColorCount = colorHistogram.GetNumberOfColors();
  57             int[] rawColors = colorHistogram.GetColors();
  58             int[] rawColorCounts = colorHistogram.GetColorCounts();
  59
  60             // First, lets pack the populations into a SparseIntArray so that they can be easily
  61             // retrieved without knowing a color's index
  62             colorPopulations = new Dictionary<int, int>();
  63
  64             for (int i = 0; i < rawColors.Length; i++)
  65             {
  66                 colorPopulations.Add(rawColors[i], rawColorCounts[i]);
  67             }
  68
  69             // Now go through all of the colors and keep those which we do not want to ignore
  70             colors = new int[rawColorCount];
  71             int validColorCount = 0;
  72
  73             foreach (int color in rawColors)
  74             {
  75                 if (!ShouldIgnoreColor(color))
  76                 {
  77                     colors[validColorCount++] = color;
  78                 }
  79             }
  80
  81             Tizen.Log.Info("Palette", "ValidColorCount = " + validColorCount + "\n");
  82             if (validColorCount <= maxColors)
  83             {
  84                 // The image has fewer colors than the maximum requested, so just return the colors
  85                 quantizedColors = new List<Palette.Swatch>();
  86
  87                 for (int i = 0; i < validColorCount; i++)
  88                 {
  89                     quantizedColors.Add(new Palette.Swatch(colors[i], colorPopulations[colors[i]]));
  90                 }
  91             }
  92             else
  93             {
  94
  95                 Tizen.Log.Info("Palette", "validColorCount = " + validColorCount + " maxColors = " + maxColors + "\n");
  96                 // We need use quantization to reduce the number of colors
  97                 quantizedColors = QuantizePixels(validColorCount - 1, maxColors);
  98             }
  99         }
 100
 101         /// <summary>
 102         /// Factory-method to generate a ColorCutQuantizer from a  PixelBuffer object.
 103         /// </summary>
 104       public static ColorCutQuantizer FromBitmap(PixelBuffer pixelBuffer, Rectangle region, int maxColors)
 105         {
 106             int width;
 107             int height;
 108             int[] pixels;
 109             int i, j, index = 0;
 110
 111             if (region == null)
 112             {
 113                 width = (int)pixelBuffer.GetWidth(); height = (int)pixelBuffer.GetHeight(); i = 0; j = 0;
 114             }
 115
 116             else
 117             {
 118                 width = region.Width; height = region.Height; i = region.X; j = region.Y;
 119             }
 120
 121             Tizen.Log.Info("Palette", "Get pixels rawdata from (" + i + " " + j + " " + width + " " + height + ")" + "\n");
 122
 123             pixels = new int[width * height];
 124             PixelFormat format = pixelBuffer.GetPixelFormat();
 125             int pixelLength = (int)ColorUtils.GetBytesPerPixel(format);
 126             IntPtr bufferIntPtr = pixelBuffer.GetBuffer();
 127
 128             unsafe
 129             {
 130                 byte *rawdata = (byte *)bufferIntPtr.ToPointer();
 131                 int totalLength = width * height * pixelLength;
 132                 for (i = 0; i < totalLength; i += pixelLength)
 133                 {
 134                     //RGB888
 135                     if (pixelLength == 3)
 136                         pixels[index++] = (255 & 0xff) << 24 | (rawdata[i] & 0xff) << 16 | (rawdata[i+1] & 0xff) << 8 | (rawdata[i+2] & 0xff);
 137                     //RGBA8888
 138                     else
 139                         pixels[index++] = (rawdata[i + 3]  & 0xff) << 24 | (rawdata[i] & 0xff) << 16 | (rawdata[i+1] & 0xff) << 8 | (rawdata[i+2] & 0xff);
 140                 }
 141             }
 142
 143             return new ColorCutQuantizer(new ColorHistogram(pixels), maxColors);
 144         }
 145
 146         /// <summary>
 147         /// return the list of quantized colors
 148         /// </summary>
 149         public List<Palette.Swatch> GetQuantizedColors()
 150         {
 151             return quantizedColors;
 152         }
 153
 154         private List<Palette.Swatch> QuantizePixels(int maxColorIndex, int maxColors)
 155         {
 156             // Create the priority queue which is sorted by volume descending. This means we always
 157             // split the largest box in the queue
 158             CustomHeap<Vbox> customHeap = new CustomHeap<Vbox>(new VboxComparatorVolume());
 159             // To start, offer a box which contains all of the colors
 160             customHeap.Offer(new Vbox(0, maxColorIndex));
 161             // Now go through the boxes, splitting them until we have reached maxColors or there are no
 162             // more boxes to split
 163             SplitBoxes(customHeap, maxColors);
 164             // Finally, return the average colors of the color boxes
 165             return GenerateAverageColors(customHeap);
 166         }
 167
 168         /// <summary>
 169         /// Iterate through the queue, popping
 170         /// ColorCutQuantizer.Vbox objects from the queue
 171         /// and splitting them. Once split, the new box and the remaining box are offered back to the
 172         /// queue.
 173         ///
 174         /// param queue PriorityQueue to poll for boxes
 175         /// param maxSize Maximum amount of boxes to split
 176         /// </summary>
 177         private void SplitBoxes(CustomHeap<Vbox> queue, int maxSize)
 178         {
 179             int i = 0;
 180             while (queue.count < maxSize)
 181             {
 182                 i++;
 183                 Vbox vbox = queue.Poll();
 184                 if (vbox != null && vbox.CanSplit())
 185                 {
 186                     // First split the box, and offer the result
 187                     queue.Offer(vbox.SplitBox());
 188                     // Then offer the box back
 189                     queue.Offer(vbox);
 190                 }
 191                 else
 192                 {
 193                     // If we get here then there are no more boxes to split, so return
 194                     return;
 195                 }
 196             }
 197         }
 198
 199         private List<Palette.Swatch> GenerateAverageColors(CustomHeap<Vbox> vboxes)
 200         {
 201             List<Palette.Swatch> colors = new List<Palette.Swatch>(vboxes.count);
 202             foreach (Vbox vbox in vboxes)
 203             {
 204                 Palette.Swatch color = vbox.GetAverageColor();
 205                 if (!ShouldIgnoreColor(color))
 206                 {
 207                     // As we're averaging a color box, we can still get colors which we do not want, so
 208                     // we check again here
 209                     colors.Add(color);
 210                 }
 211             }
 212
 213             Tizen.Log.Info("Palette", "Final generated color count = " + colors.Count + "\n");
 214             return colors;
 215         }
 216
 217         private Boolean ShouldIgnoreColor(int color)
 218         {
 219             ColorUtils.RgbToHsl((color >> 16) & 0xff, (color >> 8) & 0xff, color & 0xff, tempHsl);
 220             return ShouldIgnoreColor(tempHsl);
 221         }
 222
 223         private static Boolean ShouldIgnoreColor(Palette.Swatch color)
 224         {
 225             return ShouldIgnoreColor(color.GetHsl());
 226         }
 227
 228         private static Boolean ShouldIgnoreColor(float[] hslColor)
 229         {
 230             return IsWhite(hslColor) || IsBlack(hslColor) || IsNearRedILine(hslColor);
 231         }
 232
 233         /// <summary>
 234         ///return true if the color represents a color which is close to black.
 235         /// </summary>
 236         private static Boolean IsBlack(float[] hslColor)
 237         {
 238             return hslColor[2] <= blackMaxLightness;
 239         }
 240
 241         /// <summary>
 242         /// return true if the color represents a color which is close to white.
 243         /// </summary>
 244         private static Boolean IsWhite(float[] hslColor)
 245         {
 246             return hslColor[2] >= whiteMinLightness;
 247         }
 248
 249         /// <summary>
 250         /// return true if the color lies close to the red side of the I line.
 251         /// </summary>
 252         private static Boolean IsNearRedILine(float[] hslColor)
 253         {
 254             return hslColor[0] >= 10f && hslColor[0] <= 37f && hslColor[1] <= 0.82f;
 255         }
 256
 257         private sealed class CustomHeap<T> : IEnumerable<T>
 258         {
 259             private const int initialcapacity = 0;
 260             private const int growFactor = 2;
 261             private const int minGrow = 1;
 262
 263             private int capacity = initialcapacity;
 264             private int tail = 0;
 265             private T[] heap = Array.Empty<T>();
 266
 267             public CustomHeap(Comparer<T> comparer)
 268             {
 269                 if (comparer == null) throw new ArgumentNullException(nameof(comparer), "comparer is null");
 270                 Comparer = comparer;
 271             }
 272
 273             private Comparer<T> Comparer { get; set; }
 274
 275             public IEnumerator<T> GetEnumerator()
 276             {
 277                 return heap.Take(count).GetEnumerator();
 278             }
 279
 280             IEnumerator IEnumerable.GetEnumerator()
 281             {
 282                 return GetEnumerator();
 283             }
 284
 285             public int count { get { return tail; } }
 286
 287             public void Offer(T item)
 288             {
 289                 if (count == capacity)
 290                     Grow();
 291
 292                 heap[tail++] = item;
 293                 BubbleUp(tail - 1);
 294             }
 295
 296             public T Peek()
 297             {
 298                 if (count == 0) throw new InvalidOperationException("CustomHeap is empty");
 299                 return heap[0];
 300             }
 301
 302             public T Poll()
 303             {
 304                 if (count == 0) throw new InvalidOperationException("CustomHeap is empty");
 305                 T ret = heap[0];
 306
 307                 tail--;
 308                 Swap(tail, 0);
 309                 BubbleDown(0);
 310
 311                 return ret;
 312             }
 313
 314             private void BubbleDown(int i)
 315             {
 316                 int dominatingNode = Dominating(i);
 317
 318                 if (dominatingNode == i) return;
 319                 Swap(i, dominatingNode);
 320                 BubbleDown(dominatingNode);
 321             }
 322
 323             private void BubbleUp(int i)
 324             {
 325                 if (i == 0 || Dominates(heap[Parent(i)], heap[i]))
 326                     return;
 327
 328                 Swap(i, Parent(i));
 329                 BubbleUp(Parent(i));
 330             }
 331
 332             private int Dominating(int i)
 333             {
 334                 int dominatingNode = i;
 335
 336                 dominatingNode = GetDominating(YoungChild(i), dominatingNode);
 337                 dominatingNode = GetDominating(OldChild(i), dominatingNode);
 338                 return dominatingNode;
 339             }
 340
 341             private int GetDominating(int newNode, int dominatingNode)
 342             {
 343                 if (newNode < tail && !Dominates(heap[dominatingNode], heap[newNode]))
 344                     return newNode;
 345                 else
 346                     return dominatingNode;
 347             }
 348
 349             private void Swap(int i, int j)
 350             {
 351                 T tmp = heap[i];
 352
 353                 heap[i] = heap[j];
 354                 heap[j] = tmp;
 355             }
 356
 357             private static int Parent(int i)
 358             {
 359                 return (i + 1) / 2 - 1;
 360             }
 361
 362             private static int YoungChild(int i)
 363             {
 364                 return (i + 1) * 2 - 1;
 365             }
 366
 367             private static int OldChild(int i)
 368             {
 369                 return YoungChild(i) + 1;
 370             }
 371
 372             private void Grow()
 373             {
 374                 int newcapacity = capacity * growFactor + minGrow;
 375                 var newHeap = new T[newcapacity];
 376
 377                 Array.Copy(heap, newHeap, capacity);
 378                 heap = newHeap;
 379                 capacity = newcapacity;
 380             }
 381
 382             private bool Dominates(T x, T y)
 383             {
 384                 return Comparer.Compare(x, y) <= 0;
 385             }
 386
 387         }
 388
 389         /// <summary>
 390         /// Comparator which sorts Vbox instances based on their volume, in descending order
 391         /// </summary>
 392         private sealed class VboxComparatorVolume : Comparer<Vbox>
 393         {
 394             public override int Compare(Vbox lhs, Vbox rhs)
 395             {
 396                 return rhs.GetVolume() - lhs.GetVolume();
 397             }
 398         }
 399
 400         /// <summary>
 401         /// Represents a tightly fitting box around a color space.
 402         /// </summary>
 403         private sealed class Vbox
 404         {
 405             private int lowerIndex;
 406             private int upperIndex;
 407             private int minRed, maxRed, minGreen, maxGreen, minBlue, maxBlue;
 408
 409             public Vbox(int lowerIndex, int upperIndex)
 410             {
 411                 this.lowerIndex = lowerIndex;
 412                 this.upperIndex = upperIndex;
 413                 FitBox();
 414             }
 415
 416             public int GetVolume()
 417             {
 418                 return (maxRed - minRed + 1) * (maxGreen - minGreen + 1) * (maxBlue - minBlue + 1);
 419             }
 420
 421             public Boolean CanSplit()
 422             {
 423                 return GetColorCount() > 1;
 424             }
 425
 426             public int GetColorCount()
 427             {
 428                 return upperIndex - lowerIndex;
 429             }
 430
 431             /// <summary>
 432             /// Recomputes the boundaries of this box to tightly fit the colors within the box.
 433             /// </summary>
 434             public void FitBox()
 435             {
 436                 // Reset the min and max to opposite values
 437                 minRed = minGreen = minBlue = 0xff;
 438                 maxRed = maxGreen = maxBlue = 0x0;
 439                 for (int i = lowerIndex; i <= upperIndex; i++)
 440                 {
 441                     int red = (colors[i] >> 16) & 0xff;
 442                     int green = (colors[i] >> 8) & 0xff;
 443                     int blue = colors[i] & 0xff;
 444
 445                     maxRed = red > maxRed ? red : maxRed;
 446                     minRed = red < minRed ? red : minRed;
 447                     maxGreen = green > maxGreen ? green : maxGreen;
 448                     minGreen = green < minGreen ? green : minGreen;
 449                     maxBlue = blue > maxBlue ? blue : maxBlue;
 450                     minBlue = blue < minBlue ? blue : minBlue;
 451                 }
 452             }
 453
 454             /// <summary>
 455             /// Split this color box at the mid-point along it's longest dimension
 456             ///
 457             /// return the new ColorBox
 458             /// </summary>
 459             public Vbox SplitBox()
 460             {
 461                 if (!CanSplit())
 462                 {
 463                     throw new InvalidOperationException("Can not split a box with only 1 color");
 464                 }
 465
 466                 // find median along the longest dimension
 467                 int splitPoint = FindSplitPoint();
 468
 469                 Vbox newBox = new Vbox(splitPoint + 1, upperIndex);
 470                 // Now change this box's upperIndex and recompute the color boundaries
 471                 upperIndex = splitPoint;
 472                 FitBox();
 473
 474                 return newBox;
 475             }
 476
 477             /// <summary>
 478             /// return the dimension which this box is largest in
 479             /// </summary>
 480             public int GetLongestColorDimension()
 481             {
 482                 int redLength = maxRed - minRed;
 483                 int greenLength = maxGreen - minGreen;
 484                 int blueLength = maxBlue - minBlue;
 485
 486                 if (redLength >= greenLength && redLength >= blueLength)
 487                 {
 488                     return componentRed;
 489                 }
 490                 else if (greenLength >= redLength && greenLength >= blueLength)
 491                 {
 492                     return componentGreen;
 493                 }
 494                 else
 495                 {
 496                     return componentBlue;
 497                 }
 498             }
 499
 500             /// <summary>
 501             /// Finds the point within this box's lowerIndex and upperIndex index of where to split.
 502             ///
 503             /// This is calculated by finding the longest color dimension, and then sorting the
 504             /// sub-array based on that dimension value in each color. The colors are then iterated over
 505             /// until a color is found with at least the midpoint of the whole box's dimension midpoint.
 506             ///
 507             /// return the index of the colors array to split from
 508             /// </summary>
 509             public int FindSplitPoint()
 510             {
 511                 int longestDimension = GetLongestColorDimension();
 512
 513                 // We need to sort the colors in this box based on the longest color dimension.
 514                 // As we can't use a Comparator to define the sort logic, we modify each color so that
 515                 // it's most significant is the desired dimension
 516                 ModifySignificantOctet(longestDimension, lowerIndex, upperIndex);
 517
 518                 Array.Sort(colors, lowerIndex, upperIndex + 1 - lowerIndex);
 519
 520                 // Now revert all of the colors so that they are packed as RGB again
 521                 ModifySignificantOctet(longestDimension, lowerIndex, upperIndex);
 522
 523                 int dimensionMidPoint = MidPoint(longestDimension);
 524                 for (int i = lowerIndex; i < upperIndex; i++)
 525                 {
 526                     switch (longestDimension)
 527                     {
 528                         case componentRed:
 529                             if (((colors[i] >> 16) & 0xff) >= dimensionMidPoint)
 530                             {
 531                                 return i;
 532                             }
 533                             break;
 534                         case componentGreen:
 535                             if (((colors[i] >> 8) & 0xff) >= dimensionMidPoint)
 536                             {
 537                                 return i;
 538                             }
 539                             break;
 540                         case componentBlue:
 541                             if ((colors[i] &0xff) > dimensionMidPoint)
 542                             {
 543                                 return i;
 544                             }
 545                             break;
 546                     }
 547                 }
 548
 549                 return lowerIndex;
 550             }
 551
 552             /// <summary>
 553             /// return the average color of this box.
 554             /// </summary>
 555             public Palette.Swatch GetAverageColor()
 556             {
 557                 int redSum = 0;
 558                 int greenSum = 0;
 559                 int blueSum = 0;
 560                 int totalPopulation = 0;
 561
 562                 for (int i = lowerIndex; i <= upperIndex; i++)
 563                 {
 564                     int colorPopulation = colorPopulations[colors[i]];
 565                     totalPopulation += colorPopulation;
 566                     redSum += colorPopulation * ((colors[i] >> 16) & 0xff);
 567                     greenSum += colorPopulation * ((colors[i] >> 8) & 0xff);
 568                     blueSum += colorPopulation * (colors[i] & 0xff);
 569                 }
 570
 571                 int redAverage = (int)Math.Round(redSum / (float)totalPopulation);
 572                 int greenAverage = (int)Math.Round(greenSum / (float)totalPopulation);
 573                 int blueAverage = (int)Math.Round(blueSum / (float)totalPopulation);
 574
 575                 return new Palette.Swatch(redAverage, greenAverage, blueAverage, totalPopulation);
 576             }
 577
 578             /// <summary>
 579             /// return the midpoint of this box in the given dimension
 580             /// </summary>
 581             private int MidPoint(int dimension)
 582             {
 583                 switch (dimension)
 584                 {
 585                     case componentRed:
 586                     default:
 587                         return (minRed + maxRed) / 2;
 588                     case componentGreen:
 589                         return (minGreen + maxGreen) / 2;
 590                     case componentBlue:
 591                         return (minBlue + maxBlue) / 2;
 592                 }
 593             }
 594
 595             /// <summary>
 596             /// Modify the significant octet in a packed color int. Allows sorting based on the value of a
 597             /// single color component.
 598             ///
 599             /// see Vbox#findSplitPoint()
 600             /// </summary>
 601             private void ModifySignificantOctet(int dimension, int lowIndex, int highIndex)
 602             {
 603                 switch (dimension)
 604                 {
 605                     case componentRed:
 606                         // Already in RGB, no need to do anything
 607                         break;
 608                     case componentGreen:
 609                         // We need to do a RGB to GRB swap, or vice-versa
 610                         for (int i = lowIndex; i <= highIndex; i++)
 611                         {
 612                             int color = colors[i];
 613                             colors[i] = 255 << 24 | (color >> 8 & 0xff) << 16 | (color >> 16 & 0xff) << 8 | (color & 0xff);
 614                         }
 615
 616                         break;
 617                     case componentBlue:
 618                         // We need to do a RGB to BGR swap, or vice-versa
 619                         for (int i = lowIndex; i <= highIndex; i++)
 620                         {
 621                             int color = colors[i];
 622                             colors[i] = 255 << 24 | (color & 0xff) << 16 | (color >> 8 & 0xff) << 8 | (color >> 16 & 0xff);
 623                         }
 624                         break;
 625                 }
 626             }
 627         }
 628     }
 629 }