src/chrome/browser/thumbnails/content_analysis.cc

   1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "chrome/browser/thumbnails/content_analysis.h"
   6
   7 #include <algorithm>
   8 #include <cmath>
   9 #include <deque>
  10 #include <functional>
  11 #include <limits>
  12 #include <numeric>
  13 #include <vector>
  14
  15 #include "base/logging.h"
  16 #include "skia/ext/convolver.h"
  17 #include "skia/ext/recursive_gaussian_convolution.h"
  18 #include "third_party/skia/include/core/SkBitmap.h"
  19 #include "third_party/skia/include/core/SkSize.h"
  20 #include "ui/gfx/color_analysis.h"
  21
  22 namespace {
  23
  24 const float kSigmaThresholdForRecursive = 1.5f;
  25 const float kAspectRatioToleranceFactor = 1.02f;
  26
  27 template<class InputIterator, class OutputIterator, class Compare>
  28 void SlidingWindowMinMax(InputIterator first,
  29                          InputIterator last,
  30                          OutputIterator output,
  31                          int window_size,
  32                          Compare cmp) {
  33   typedef std::deque<
  34       std::pair<typename std::iterator_traits<InputIterator>::value_type, int> >
  35           deque_type;
  36   deque_type slider;
  37   int front_tail_length = window_size / 2;
  38   int i = 0;
  39   DCHECK_LT(front_tail_length, last - first);
  40   // This min-max filter functions the way image filters do. The min/max we
  41   // compute is placed in the center of the window. Thus, first we need to
  42   // 'pre-load' the window with the slider with right-tail of the filter.
  43   for (; first < last && i < front_tail_length; ++i, ++first)
  44     slider.push_back(std::make_pair(*first, i));
  45
  46   for (; first < last; ++i, ++first, ++output) {
  47     while (!slider.empty() && !cmp(slider.back().first, *first))
  48       slider.pop_back();
  49     slider.push_back(std::make_pair(*first, i));
  50
  51     while (slider.front().second <= i - window_size)
  52       slider.pop_front();
  53     *output = slider.front().first;
  54   }
  55
  56   // Now at the tail-end we will simply need to use whatever value is left of
  57   // the filter to compute the remaining front_tail_length taps in the output.
  58
  59   // If input shorter than window, remainder length needs to be adjusted.
  60   front_tail_length = std::min(front_tail_length, i);
  61   for (; front_tail_length >= 0; --front_tail_length, ++i) {
  62     while (slider.front().second <= i - window_size)
  63       slider.pop_front();
  64     *output = slider.front().first;
  65   }
  66 }
  67
  68 size_t FindOtsuThresholdingIndex(const std::vector<int>& histogram) {
  69   // Otsu's method seeks to maximize variance between two classes of pixels
  70   // correspondng to valleys and peaks of the profile.
  71   double w1 = histogram[0];  // Total weight of the first class.
  72   double t1 = 0.5 * w1;
  73   double w2 = 0.0;
  74   double t2 = 0.0;
  75   for (size_t i = 1; i < histogram.size(); ++i) {
  76     w2 += histogram[i];
  77     t2 += (0.5 + i) * histogram[i];
  78   }
  79
  80   size_t max_index = 0;
  81   double m1 = t1 / w1;
  82   double m2 = t2 / w2;
  83   double max_variance_score = w1 * w2 * (m1 - m2) * (m1 - m2);
  84   // Iterate through all possible ways of splitting the histogram.
  85   for (size_t i = 1; i < histogram.size() - 1; i++) {
  86     double bin_volume = (0.5 + i) * histogram[i];
  87     w1 += histogram[i];
  88     w2 -= histogram[i];
  89     t2 -= bin_volume;
  90     t1 += bin_volume;
  91     m1 = t1 / w1;
  92     m2 = t2 / w2;
  93     double variance_score = w1 * w2 * (m1 - m2) * (m1 - m2);
  94     if (variance_score >= max_variance_score) {
  95       max_variance_score = variance_score;
  96       max_index = i;
  97     }
  98   }
  99
 100   return max_index;
 101 }
 102
 103 bool ComputeScaledHistogram(const std::vector<float>& source,
 104                             std::vector<int>* histogram,
 105                             std::pair<float, float>* minmax) {
 106   DCHECK(histogram);
 107   DCHECK(minmax);
 108   histogram->clear();
 109   histogram->resize(256);
 110   float value_min = std::numeric_limits<float>::max();
 111   float value_max = 0.0f;
 112
 113   std::vector<float>::const_iterator it;
 114   for (it = source.begin(); it < source.end(); ++it) {
 115     value_min = std::min(value_min, *it);
 116     value_max = std::max(value_max, *it);
 117   }
 118
 119   *minmax = std::make_pair(value_min, value_max);
 120
 121   if (value_max - value_min <= std::numeric_limits<float>::epsilon() * 100.0f) {
 122     // Scaling won't work and there is nothing really to segment anyway.
 123     return false;
 124   }
 125
 126   float value_span = value_max - value_min;
 127   float scale = 255.0f / value_span;
 128   for (it = source.begin(); it < source.end(); ++it) {
 129     float scaled_value = (*it - value_min) * scale;
 130     (*histogram)[static_cast<int>(scaled_value)] += 1;
 131   }
 132   return true;
 133 }
 134
 135 void ConstrainedProfileThresholding(const std::vector<float>& profile,
 136                                     const std::vector<int>& histogram,
 137                                     int current_clip_index,
 138                                     float current_threshold,
 139                                     const std::pair<float, float>& range,
 140                                     int size_for_threshold,
 141                                     int target_size,
 142                                     std::vector<bool>* result) {
 143   DCHECK(!profile.empty());
 144   DCHECK_EQ(histogram.size(), 256U);
 145   DCHECK(result);
 146
 147   // A subroutine performing thresholding on the |profile|.
 148   if (size_for_threshold != target_size) {
 149     // Find a cut-off point (on the histogram) closest to the desired size.
 150     int candidate_size = profile.size();
 151     int candidate_clip_index = 0;
 152     for (std::vector<int>::const_iterator it = histogram.begin();
 153          it != histogram.end(); ++it, ++candidate_clip_index) {
 154       if (std::abs(candidate_size - target_size) <
 155           std::abs(candidate_size - *it - target_size)) {
 156         break;
 157       }
 158       candidate_size -= *it;
 159     }
 160
 161     if (std::abs(candidate_size - target_size) <
 162         std::abs(candidate_size -size_for_threshold)) {
 163       current_clip_index = candidate_clip_index;
 164       current_threshold =  (range.second - range.first) *
 165           current_clip_index / 255.0f + range.first;
 166       // Recount, rather than assume. One-offs due to rounding can be very
 167       // harmful when eroding / dilating the result.
 168       size_for_threshold = std::count_if(
 169           profile.begin(), profile.end(),
 170           std::bind2nd(std::greater<float>(), current_threshold));
 171     }
 172   }
 173
 174   result->resize(profile.size());
 175   for (size_t i = 0; i < profile.size(); ++i)
 176     (*result)[i] = profile[i] > current_threshold;
 177
 178   while (size_for_threshold > target_size) {
 179     // If the current size is larger than target size, erode exactly as needed.
 180     std::vector<bool>::iterator mod_it = result->begin();
 181     std::vector<bool>::const_iterator lead_it = result->begin();
 182     bool prev_value = true;
 183     for (++lead_it;
 184          lead_it < result->end() && size_for_threshold > target_size;
 185          ++lead_it, ++mod_it) {
 186       bool value = *mod_it;
 187       // If any neighbour is false, switch the element off.
 188       if (!prev_value || !*lead_it) {
 189         *mod_it = false;
 190         --size_for_threshold;
 191       }
 192       prev_value = value;
 193     }
 194
 195     if (lead_it == result->end() && !prev_value) {
 196       *mod_it = false;
 197       --size_for_threshold;
 198     }
 199   }
 200
 201   while (size_for_threshold < target_size) {
 202     std::vector<bool>::iterator mod_it = result->begin();
 203     std::vector<bool>::const_iterator lead_it = result->begin();
 204     bool prev_value = false;
 205     for (++lead_it;
 206          lead_it < result->end() && size_for_threshold < target_size;
 207          ++lead_it, ++mod_it) {
 208       bool value = *mod_it;
 209       // If any neighbour is false, switch the element off.
 210       if (!prev_value || !*lead_it) {
 211         *mod_it = true;
 212         ++size_for_threshold;
 213       }
 214       prev_value = value;
 215     }
 216
 217     if (lead_it == result->end() && !prev_value) {
 218       *mod_it = true;
 219       ++size_for_threshold;
 220     }
 221   }
 222 }
 223
 224 }  // namespace
 225
 226 namespace thumbnailing_utils {
 227
 228 void ApplyGaussianGradientMagnitudeFilter(SkBitmap* input_bitmap,
 229                                           float kernel_sigma) {
 230   // The purpose of this function is to highlight salient
 231   // (attention-attracting?) features of the image for use in image
 232   // retargeting.
 233   SkAutoLockPixels source_lock(*input_bitmap);
 234   DCHECK(input_bitmap);
 235   DCHECK(input_bitmap->getPixels());
 236   DCHECK_EQ(kAlpha_8_SkColorType, input_bitmap->colorType());
 237
 238   // To perform computations we will need one intermediate buffer. It can
 239   // very well be just another bitmap.
 240   const SkISize image_size = SkISize::Make(input_bitmap->width(),
 241                                            input_bitmap->height());
 242   SkBitmap intermediate;
 243   intermediate.allocPixels(input_bitmap->info().makeWH(image_size.width(),
 244                                                        image_size.height()));
 245
 246   SkBitmap intermediate2;
 247   intermediate2.allocPixels(input_bitmap->info().makeWH(image_size.width(),
 248                                                         image_size.height()));
 249
 250   if (kernel_sigma <= kSigmaThresholdForRecursive) {
 251     // For small kernels classic implementation is faster.
 252     skia::ConvolutionFilter1D smoothing_filter;
 253     skia::SetUpGaussianConvolutionKernel(
 254         &smoothing_filter, kernel_sigma, false);
 255     skia::SingleChannelConvolveX1D(
 256         input_bitmap->getAddr8(0, 0),
 257         static_cast<int>(input_bitmap->rowBytes()),
 258         0, input_bitmap->bytesPerPixel(),
 259         smoothing_filter,
 260         image_size,
 261         intermediate.getAddr8(0, 0),
 262         static_cast<int>(intermediate.rowBytes()),
 263         0, intermediate.bytesPerPixel(), false);
 264     skia::SingleChannelConvolveY1D(
 265         intermediate.getAddr8(0, 0),
 266         static_cast<int>(intermediate.rowBytes()),
 267         0, intermediate.bytesPerPixel(),
 268         smoothing_filter,
 269         image_size,
 270         input_bitmap->getAddr8(0, 0),
 271         static_cast<int>(input_bitmap->rowBytes()),
 272         0, input_bitmap->bytesPerPixel(), false);
 273
 274     skia::ConvolutionFilter1D gradient_filter;
 275     skia::SetUpGaussianConvolutionKernel(&gradient_filter, kernel_sigma, true);
 276     skia::SingleChannelConvolveX1D(
 277         input_bitmap->getAddr8(0, 0),
 278         static_cast<int>(input_bitmap->rowBytes()),
 279         0, input_bitmap->bytesPerPixel(),
 280         gradient_filter,
 281         image_size,
 282         intermediate.getAddr8(0, 0),
 283         static_cast<int>(intermediate.rowBytes()),
 284         0, intermediate.bytesPerPixel(), true);
 285     skia::SingleChannelConvolveY1D(
 286         input_bitmap->getAddr8(0, 0),
 287         static_cast<int>(input_bitmap->rowBytes()),
 288         0, input_bitmap->bytesPerPixel(),
 289         gradient_filter,
 290         image_size,
 291         intermediate2.getAddr8(0, 0),
 292         static_cast<int>(intermediate2.rowBytes()),
 293         0, intermediate2.bytesPerPixel(), true);
 294   } else {
 295     // For larger sigma values use the recursive filter.
 296     skia::RecursiveFilter smoothing_filter(kernel_sigma,
 297                                            skia::RecursiveFilter::FUNCTION);
 298     skia::SingleChannelRecursiveGaussianX(
 299         input_bitmap->getAddr8(0, 0),
 300         static_cast<int>(input_bitmap->rowBytes()),
 301         0, input_bitmap->bytesPerPixel(),
 302         smoothing_filter,
 303         image_size,
 304         intermediate.getAddr8(0, 0),
 305         static_cast<int>(intermediate.rowBytes()),
 306         0, intermediate.bytesPerPixel(), false);
 307     unsigned char smoothed_max = skia::SingleChannelRecursiveGaussianY(
 308         intermediate.getAddr8(0, 0),
 309         static_cast<int>(intermediate.rowBytes()),
 310         0, intermediate.bytesPerPixel(),
 311         smoothing_filter,
 312         image_size,
 313         input_bitmap->getAddr8(0, 0),
 314         static_cast<int>(input_bitmap->rowBytes()),
 315         0, input_bitmap->bytesPerPixel(), false);
 316     if (smoothed_max < 127) {
 317       int bit_shift = 8 - static_cast<int>(
 318           std::log10(static_cast<float>(smoothed_max)) / std::log10(2.0f));
 319       for (int r = 0; r < image_size.height(); ++r) {
 320         uint8* row = input_bitmap->getAddr8(0, r);
 321         for (int c = 0; c < image_size.width(); ++c, ++row) {
 322           *row <<= bit_shift;
 323         }
 324       }
 325     }
 326
 327     skia::RecursiveFilter gradient_filter(
 328         kernel_sigma, skia::RecursiveFilter::FIRST_DERIVATIVE);
 329     skia::SingleChannelRecursiveGaussianX(
 330         input_bitmap->getAddr8(0, 0),
 331         static_cast<int>(input_bitmap->rowBytes()),
 332         0, input_bitmap->bytesPerPixel(),
 333         gradient_filter,
 334         image_size,
 335         intermediate.getAddr8(0, 0),
 336         static_cast<int>(intermediate.rowBytes()),
 337         0, intermediate.bytesPerPixel(), true);
 338     skia::SingleChannelRecursiveGaussianY(
 339         input_bitmap->getAddr8(0, 0),
 340         static_cast<int>(input_bitmap->rowBytes()),
 341         0, input_bitmap->bytesPerPixel(),
 342         gradient_filter,
 343         image_size,
 344         intermediate2.getAddr8(0, 0),
 345         static_cast<int>(intermediate2.rowBytes()),
 346         0, intermediate2.bytesPerPixel(), true);
 347   }
 348
 349   unsigned grad_max = 0;
 350   for (int r = 0; r < image_size.height(); ++r) {
 351     const uint8* grad_x_row = intermediate.getAddr8(0, r);
 352     const uint8* grad_y_row = intermediate2.getAddr8(0, r);
 353     for (int c = 0; c < image_size.width(); ++c) {
 354       unsigned grad_x = grad_x_row[c];
 355       unsigned grad_y = grad_y_row[c];
 356       grad_max = std::max(grad_max, grad_x * grad_x + grad_y * grad_y);
 357     }
 358   }
 359
 360   int bit_shift = 0;
 361   if (grad_max > 255)
 362     bit_shift = static_cast<int>(
 363         std::log10(static_cast<float>(grad_max)) / std::log10(2.0f)) - 7;
 364   for (int r = 0; r < image_size.height(); ++r) {
 365     const uint8* grad_x_row = intermediate.getAddr8(0, r);
 366     const uint8* grad_y_row = intermediate2.getAddr8(0, r);
 367     uint8* target_row = input_bitmap->getAddr8(0, r);
 368     for (int c = 0; c < image_size.width(); ++c) {
 369       unsigned grad_x = grad_x_row[c];
 370       unsigned grad_y = grad_y_row[c];
 371       target_row[c] = (grad_x * grad_x + grad_y * grad_y) >> bit_shift;
 372     }
 373   }
 374 }
 375
 376 void ExtractImageProfileInformation(const SkBitmap& input_bitmap,
 377                                     const gfx::Rect& area,
 378                                     const gfx::Size& target_size,
 379                                     bool apply_log,
 380                                     std::vector<float>* rows,
 381                                     std::vector<float>* columns) {
 382   SkAutoLockPixels source_lock(input_bitmap);
 383   DCHECK(rows);
 384   DCHECK(columns);
 385   DCHECK(input_bitmap.getPixels());
 386   DCHECK_EQ(kAlpha_8_SkColorType, input_bitmap.colorType());
 387   DCHECK_GE(area.x(), 0);
 388   DCHECK_GE(area.y(), 0);
 389   DCHECK_LE(area.right(), input_bitmap.width());
 390   DCHECK_LE(area.bottom(), input_bitmap.height());
 391
 392   // Make sure rows and columns are allocated and initialized to 0.
 393   rows->clear();
 394   columns->clear();
 395   rows->resize(area.height(), 0);
 396   columns->resize(area.width(), 0);
 397
 398   for (int r = 0; r < area.height(); ++r) {
 399     // Points to the first byte of the row in the rectangle.
 400     const uint8* image_row = input_bitmap.getAddr8(area.x(), r + area.y());
 401     unsigned row_sum = 0;
 402     for (int c = 0; c < area.width(); ++c, ++image_row) {
 403       row_sum += *image_row;
 404       (*columns)[c] += *image_row;
 405     }
 406     (*rows)[r] = row_sum;
 407   }
 408
 409   if (apply_log) {
 410     // Generally for processing we will need to take logarithm of this data.
 411     // The option not to apply it is left principally as a test seam.
 412     std::vector<float>::iterator it;
 413     for (it = columns->begin(); it < columns->end(); ++it)
 414       *it = std::log(1.0f + *it);
 415
 416     for (it = rows->begin(); it < rows->end(); ++it)
 417       *it = std::log(1.0f + *it);
 418   }
 419
 420   if (!target_size.IsEmpty()) {
 421     // If the target size is given, profiles should be further processed through
 422     // morphological closing. The idea is to close valleys smaller than what
 423     // can be seen after scaling down to avoid deforming noticable features
 424     // when profiles are used.
 425     // Morphological closing is defined as dilation followed by errosion. In
 426     // normal-speak: sliding-window maximum followed by minimum.
 427     int column_window_size = 1 + 2 *
 428         static_cast<int>(0.5f * area.width() / target_size.width() + 0.5f);
 429     int row_window_size = 1 + 2 *
 430         static_cast<int>(0.5f * area.height() / target_size.height() + 0.5f);
 431
 432     // Dilate and erode each profile with the given window size.
 433     if (column_window_size >= 3) {
 434       SlidingWindowMinMax(columns->begin(),
 435                           columns->end(),
 436                           columns->begin(),
 437                           column_window_size,
 438                           std::greater<float>());
 439       SlidingWindowMinMax(columns->begin(),
 440                           columns->end(),
 441                           columns->begin(),
 442                           column_window_size,
 443                           std::less<float>());
 444     }
 445
 446     if (row_window_size >= 3) {
 447       SlidingWindowMinMax(rows->begin(),
 448                           rows->end(),
 449                           rows->begin(),
 450                           row_window_size,
 451                           std::greater<float>());
 452       SlidingWindowMinMax(rows->begin(),
 453                           rows->end(),
 454                           rows->begin(),
 455                           row_window_size,
 456                           std::less<float>());
 457     }
 458   }
 459 }
 460
 461 float AutoSegmentPeaks(const std::vector<float>& input) {
 462   // This is a thresholding operation based on Otsu's method.
 463   std::vector<int> histogram;
 464   std::pair<float, float> minmax;
 465   if (!ComputeScaledHistogram(input, &histogram, &minmax))
 466     return minmax.first;
 467
 468   // max_index refers to the bin *after* which we need to split. The sought
 469   // threshold is the centre of this bin, scaled back to the original range.
 470   size_t max_index = FindOtsuThresholdingIndex(histogram);
 471   return (minmax.second - minmax.first) * (max_index + 0.5f) / 255.0f +
 472       minmax.first;
 473 }
 474
 475 gfx::Size AdjustClippingSizeToAspectRatio(const gfx::Size& target_size,
 476                                           const gfx::Size& image_size,
 477                                           const gfx::Size& computed_size) {
 478   DCHECK_GT(target_size.width(), 0);
 479   DCHECK_GT(target_size.height(), 0);
 480   // If the computed thumbnail would be too wide or to tall, we shall attempt
 481   // to fix it. Generally the idea is to re-add content to the part which has
 482   // been more aggressively shrunk unless there is nothing to add there or if
 483   // adding there won't fix anything. Should that be the case,  we will
 484   // (reluctantly) take away more from the other dimension.
 485   float desired_aspect =
 486       static_cast<float>(target_size.width()) / target_size.height();
 487   int computed_width = std::max(computed_size.width(), target_size.width());
 488   int computed_height = std::max(computed_size.height(), target_size.height());
 489   float computed_aspect = static_cast<float>(computed_width) / computed_height;
 490   float aspect_change_delta = std::abs(computed_aspect - desired_aspect);
 491   float prev_aspect_change_delta = 1000.0f;
 492   const float kAspectChangeEps = 0.01f;
 493   const float kLargeEffect = 2.0f;
 494
 495   while ((prev_aspect_change_delta - aspect_change_delta > kAspectChangeEps) &&
 496          (computed_aspect / desired_aspect > kAspectRatioToleranceFactor ||
 497           desired_aspect / computed_aspect > kAspectRatioToleranceFactor)) {
 498     int new_computed_width = computed_width;
 499     int new_computed_height = computed_height;
 500     float row_dimension_shrink =
 501         static_cast<float>(image_size.height()) / computed_height;
 502     float column_dimension_shrink =
 503         static_cast<float>(image_size.width()) / computed_width;
 504
 505     if (computed_aspect / desired_aspect > kAspectRatioToleranceFactor) {
 506       // Too wide.
 507       if (row_dimension_shrink > column_dimension_shrink) {
 508         // Bring the computed_height to the least of:
 509         // (1) image height (2) the number of lines that would
 510         // make up the desired aspect or (3) number of lines we would get
 511         // at the same 'aggressivity' level as width or.
 512         new_computed_height = std::min(
 513             static_cast<int>(image_size.height()),
 514             static_cast<int>(computed_width / desired_aspect + 0.5f));
 515         new_computed_height = std::min(
 516             new_computed_height,
 517             static_cast<int>(
 518                 image_size.height() / column_dimension_shrink + 0.5f));
 519       } else if (row_dimension_shrink >= kLargeEffect ||
 520                  new_computed_width <= target_size.width()) {
 521         // Even though rows were resized less, we will generally rather add than
 522         // remove (or there is nothing to remove in x already).
 523         new_computed_height = std::min(
 524             static_cast<int>(image_size.height()),
 525             static_cast<int>(computed_width / desired_aspect + 0.5f));
 526       } else {
 527         // Rows were already shrunk less aggressively. This means there is
 528         // simply no room left too expand. Cut columns to get the desired
 529         // aspect ratio.
 530         new_computed_width = desired_aspect * computed_height + 0.5f;
 531       }
 532     } else {
 533       // Too tall.
 534       if (column_dimension_shrink > row_dimension_shrink) {
 535         // Columns were shrunk more aggressively. Try to relax the same way as
 536         // above.
 537         new_computed_width = std::min(
 538             static_cast<int>(image_size.width()),
 539             static_cast<int>(desired_aspect * computed_height + 0.5f));
 540         new_computed_width = std::min(
 541             new_computed_width,
 542             static_cast<int>(
 543                 image_size.width() / row_dimension_shrink  + 0.5f));
 544       } else if (column_dimension_shrink  >= kLargeEffect ||
 545                  new_computed_height <= target_size.height()) {
 546         new_computed_width = std::min(
 547             static_cast<int>(image_size.width()),
 548             static_cast<int>(desired_aspect * computed_height + 0.5f));
 549       } else {
 550         new_computed_height = computed_width / desired_aspect + 0.5f;
 551       }
 552     }
 553
 554     new_computed_width = std::max(new_computed_width, target_size.width());
 555     new_computed_height = std::max(new_computed_height, target_size.height());
 556
 557     // Update loop control variables.
 558     float new_computed_aspect =
 559         static_cast<float>(new_computed_width) / new_computed_height;
 560
 561     if (std::abs(new_computed_aspect - desired_aspect) >
 562         std::abs(computed_aspect - desired_aspect)) {
 563       // Do not take inferior results.
 564       break;
 565     }
 566
 567     computed_width = new_computed_width;
 568     computed_height = new_computed_height;
 569     computed_aspect = new_computed_aspect;
 570     prev_aspect_change_delta = aspect_change_delta;
 571     aspect_change_delta = std::abs(new_computed_aspect - desired_aspect);
 572   }
 573
 574   return gfx::Size(computed_width, computed_height);
 575 }
 576
 577 void ConstrainedProfileSegmentation(const std::vector<float>& row_profile,
 578                                     const std::vector<float>& column_profile,
 579                                     const gfx::Size& target_size,
 580                                     std::vector<bool>* included_rows,
 581                                     std::vector<bool>* included_columns) {
 582   DCHECK(included_rows);
 583   DCHECK(included_columns);
 584
 585   std::vector<int> histogram_rows;
 586   std::pair<float, float> minmax_rows;
 587   bool rows_well_behaved = ComputeScaledHistogram(
 588       row_profile, &histogram_rows, &minmax_rows);
 589
 590   float row_threshold = minmax_rows.first;
 591   size_t clip_index_rows = 0;
 592
 593   if (rows_well_behaved) {
 594     clip_index_rows = FindOtsuThresholdingIndex(histogram_rows);
 595     row_threshold = (minmax_rows.second - minmax_rows.first) *
 596         (clip_index_rows + 0.5f) / 255.0f + minmax_rows.first;
 597   }
 598
 599   std::vector<int> histogram_columns;
 600   std::pair<float, float> minmax_columns;
 601   bool columns_well_behaved = ComputeScaledHistogram(column_profile,
 602                                                      &histogram_columns,
 603                                                      &minmax_columns);
 604   float column_threshold = minmax_columns.first;
 605   size_t clip_index_columns = 0;
 606
 607   if (columns_well_behaved) {
 608     clip_index_columns = FindOtsuThresholdingIndex(histogram_columns);
 609     column_threshold = (minmax_columns.second - minmax_columns.first) *
 610         (clip_index_columns + 0.5f) / 255.0f + minmax_columns.first;
 611   }
 612
 613   int auto_segmented_width = count_if(
 614       column_profile.begin(), column_profile.end(),
 615       std::bind2nd(std::greater<float>(), column_threshold));
 616   int auto_segmented_height = count_if(
 617       row_profile.begin(), row_profile.end(),
 618       std::bind2nd(std::greater<float>(), row_threshold));
 619
 620   gfx::Size computed_size = AdjustClippingSizeToAspectRatio(
 621       target_size,
 622       gfx::Size(column_profile.size(), row_profile.size()),
 623       gfx::Size(auto_segmented_width, auto_segmented_height));
 624
 625   // Apply thresholding.
 626   if (rows_well_behaved) {
 627     ConstrainedProfileThresholding(row_profile,
 628                                    histogram_rows,
 629                                    clip_index_rows,
 630                                    row_threshold,
 631                                    minmax_rows,
 632                                    auto_segmented_height,
 633                                    computed_size.height(),
 634                                    included_rows);
 635   } else {
 636     // This is essentially an error condition, invoked when no segmentation was
 637     // possible. This will result in applying a very low threshold and likely
 638     // in producing a thumbnail which should get rejected.
 639     included_rows->resize(row_profile.size());
 640     for (size_t i = 0; i < row_profile.size(); ++i)
 641       (*included_rows)[i] = row_profile[i] > row_threshold;
 642   }
 643
 644   if (columns_well_behaved) {
 645     ConstrainedProfileThresholding(column_profile,
 646                                    histogram_columns,
 647                                    clip_index_columns,
 648                                    column_threshold,
 649                                    minmax_columns,
 650                                    auto_segmented_width,
 651                                    computed_size.width(),
 652                                    included_columns);
 653   } else {
 654     included_columns->resize(column_profile.size());
 655     for (size_t i = 0; i < column_profile.size(); ++i)
 656       (*included_columns)[i] = column_profile[i] > column_threshold;
 657   }
 658 }
 659
 660 SkBitmap ComputeDecimatedImage(const SkBitmap& bitmap,
 661                                const std::vector<bool>& rows,
 662                                const std::vector<bool>& columns) {
 663   SkAutoLockPixels source_lock(bitmap);
 664   DCHECK(bitmap.getPixels());
 665   DCHECK_GT(bitmap.bytesPerPixel(), 0);
 666   DCHECK_EQ(bitmap.width(), static_cast<int>(columns.size()));
 667   DCHECK_EQ(bitmap.height(), static_cast<int>(rows.size()));
 668
 669   unsigned target_row_count = std::count(rows.begin(), rows.end(), true);
 670   unsigned target_column_count = std::count(
 671       columns.begin(), columns.end(), true);
 672
 673   if (target_row_count == 0 || target_column_count == 0)
 674     return SkBitmap();  // Not quite an error, so no DCHECK. Just return empty.
 675
 676   if (target_row_count == rows.size() && target_column_count == columns.size())
 677     return SkBitmap();  // Equivalent of the situation above (empty target).
 678
 679   // Allocate the target image.
 680   SkBitmap target;
 681   target.allocPixels(bitmap.info().makeWH(target_column_count,
 682                                           target_row_count));
 683
 684   int target_row = 0;
 685   for (int r = 0; r < bitmap.height(); ++r) {
 686     if (!rows[r])
 687       continue;  // We can just skip this one.
 688     uint8* src_row =
 689         static_cast<uint8*>(bitmap.getPixels()) + r * bitmap.rowBytes();
 690     uint8* insertion_target = static_cast<uint8*>(target.getPixels()) +
 691         target_row * target.rowBytes();
 692     int left_copy_pixel = -1;
 693     for (int c = 0; c < bitmap.width(); ++c) {
 694       if (left_copy_pixel < 0 && columns[c]) {
 695         left_copy_pixel = c;  // Next time we will start copying from here.
 696       } else if (left_copy_pixel >= 0 && !columns[c]) {
 697         // This closes a fragment we want to copy. We do it now.
 698         size_t bytes_to_copy = (c - left_copy_pixel) * bitmap.bytesPerPixel();
 699         memcpy(insertion_target,
 700                src_row + left_copy_pixel * bitmap.bytesPerPixel(),
 701                bytes_to_copy);
 702         left_copy_pixel = -1;
 703         insertion_target += bytes_to_copy;
 704       }
 705     }
 706     // We can still have the tail end to process here.
 707     if (left_copy_pixel >= 0) {
 708       size_t bytes_to_copy =
 709           (bitmap.width() - left_copy_pixel) * bitmap.bytesPerPixel();
 710       memcpy(insertion_target,
 711              src_row + left_copy_pixel * bitmap.bytesPerPixel(),
 712              bytes_to_copy);
 713     }
 714     target_row++;
 715   }
 716
 717   return target;
 718 }
 719
 720 SkBitmap CreateRetargetedThumbnailImage(
 721     const SkBitmap& source_bitmap,
 722     const gfx::Size& target_size,
 723     float kernel_sigma) {
 724   // First thing we need for this method is to color-reduce the source_bitmap.
 725   SkBitmap reduced_color;
 726   reduced_color.allocPixels(SkImageInfo::MakeA8(source_bitmap.width(),
 727                                                 source_bitmap.height()));
 728
 729   if (!color_utils::ComputePrincipalComponentImage(source_bitmap,
 730                                                    &reduced_color)) {
 731     // CCIR601 luminance conversion vector.
 732     gfx::Vector3dF transform(0.299f, 0.587f, 0.114f);
 733     if (!color_utils::ApplyColorReduction(
 734             source_bitmap, transform, true, &reduced_color)) {
 735       DLOG(WARNING) << "Failed to compute luminance image from a screenshot. "
 736                     << "Cannot compute retargeted thumbnail.";
 737       return SkBitmap();
 738     }
 739     DLOG(WARNING) << "Could not compute principal color image for a thumbnail. "
 740                   << "Using luminance instead.";
 741   }
 742
 743   // Turn 'color-reduced' image into the 'energy' image.
 744   ApplyGaussianGradientMagnitudeFilter(&reduced_color, kernel_sigma);
 745
 746   // Extract vertical and horizontal projection of image features.
 747   std::vector<float> row_profile;
 748   std::vector<float> column_profile;
 749   ExtractImageProfileInformation(reduced_color,
 750                                  gfx::Rect(reduced_color.width(),
 751                                            reduced_color.height()),
 752                                  target_size,
 753                                  true,
 754                                  &row_profile,
 755                                  &column_profile);
 756
 757   std::vector<bool> included_rows, included_columns;
 758   ConstrainedProfileSegmentation(row_profile,
 759                                  column_profile,
 760                                  target_size,
 761                                  &included_rows,
 762                                  &included_columns);
 763
 764   // Use the original image and computed inclusion vectors to create a resized
 765   // image.
 766   return ComputeDecimatedImage(source_bitmap, included_rows, included_columns);
 767 }
 768
 769 }  // thumbnailing_utils