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
22namespace {
23
24const float kSigmaThresholdForRecursive = 1.5f;
25const float kAspectRatioToleranceFactor = 1.02f;
26
27template<class InputIterator, class OutputIterator, class Compare>
28void 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
68size_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
103bool 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
135void 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
226namespace thumbnailing_utils {
227
228void 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(SkBitmap::kA8_Config, input_bitmap->config());
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.setConfig(
244      input_bitmap->config(), image_size.width(), image_size.height());
245  intermediate.allocPixels();
246
247  SkBitmap intermediate2;
248  intermediate2.setConfig(
249      input_bitmap->config(), image_size.width(), image_size.height());
250  intermediate2.allocPixels();
251
252
253  if (kernel_sigma <= kSigmaThresholdForRecursive) {
254    // For small kernels classic implementation is faster.
255    skia::ConvolutionFilter1D smoothing_filter;
256    skia::SetUpGaussianConvolutionKernel(
257        &smoothing_filter, kernel_sigma, false);
258    skia::SingleChannelConvolveX1D(
259        input_bitmap->getAddr8(0, 0),
260        static_cast<int>(input_bitmap->rowBytes()),
261        0, input_bitmap->bytesPerPixel(),
262        smoothing_filter,
263        image_size,
264        intermediate.getAddr8(0, 0),
265        static_cast<int>(intermediate.rowBytes()),
266        0, intermediate.bytesPerPixel(), false);
267    skia::SingleChannelConvolveY1D(
268        intermediate.getAddr8(0, 0),
269        static_cast<int>(intermediate.rowBytes()),
270        0, intermediate.bytesPerPixel(),
271        smoothing_filter,
272        image_size,
273        input_bitmap->getAddr8(0, 0),
274        static_cast<int>(input_bitmap->rowBytes()),
275        0, input_bitmap->bytesPerPixel(), false);
276
277    skia::ConvolutionFilter1D gradient_filter;
278    skia::SetUpGaussianConvolutionKernel(&gradient_filter, kernel_sigma, true);
279    skia::SingleChannelConvolveX1D(
280        input_bitmap->getAddr8(0, 0),
281        static_cast<int>(input_bitmap->rowBytes()),
282        0, input_bitmap->bytesPerPixel(),
283        gradient_filter,
284        image_size,
285        intermediate.getAddr8(0, 0),
286        static_cast<int>(intermediate.rowBytes()),
287        0, intermediate.bytesPerPixel(), true);
288    skia::SingleChannelConvolveY1D(
289        input_bitmap->getAddr8(0, 0),
290        static_cast<int>(input_bitmap->rowBytes()),
291        0, input_bitmap->bytesPerPixel(),
292        gradient_filter,
293        image_size,
294        intermediate2.getAddr8(0, 0),
295        static_cast<int>(intermediate2.rowBytes()),
296        0, intermediate2.bytesPerPixel(), true);
297  } else {
298    // For larger sigma values use the recursive filter.
299    skia::RecursiveFilter smoothing_filter(kernel_sigma,
300                                           skia::RecursiveFilter::FUNCTION);
301    skia::SingleChannelRecursiveGaussianX(
302        input_bitmap->getAddr8(0, 0),
303        static_cast<int>(input_bitmap->rowBytes()),
304        0, input_bitmap->bytesPerPixel(),
305        smoothing_filter,
306        image_size,
307        intermediate.getAddr8(0, 0),
308        static_cast<int>(intermediate.rowBytes()),
309        0, intermediate.bytesPerPixel(), false);
310    unsigned char smoothed_max = skia::SingleChannelRecursiveGaussianY(
311        intermediate.getAddr8(0, 0),
312        static_cast<int>(intermediate.rowBytes()),
313        0, intermediate.bytesPerPixel(),
314        smoothing_filter,
315        image_size,
316        input_bitmap->getAddr8(0, 0),
317        static_cast<int>(input_bitmap->rowBytes()),
318        0, input_bitmap->bytesPerPixel(), false);
319    if (smoothed_max < 127) {
320      int bit_shift = 8 - static_cast<int>(
321          std::log10(static_cast<float>(smoothed_max)) / std::log10(2.0f));
322      for (int r = 0; r < image_size.height(); ++r) {
323        uint8* row = input_bitmap->getAddr8(0, r);
324        for (int c = 0; c < image_size.width(); ++c, ++row) {
325          *row <<= bit_shift;
326        }
327      }
328    }
329
330    skia::RecursiveFilter gradient_filter(
331        kernel_sigma, skia::RecursiveFilter::FIRST_DERIVATIVE);
332    skia::SingleChannelRecursiveGaussianX(
333        input_bitmap->getAddr8(0, 0),
334        static_cast<int>(input_bitmap->rowBytes()),
335        0, input_bitmap->bytesPerPixel(),
336        gradient_filter,
337        image_size,
338        intermediate.getAddr8(0, 0),
339        static_cast<int>(intermediate.rowBytes()),
340        0, intermediate.bytesPerPixel(), true);
341    skia::SingleChannelRecursiveGaussianY(
342        input_bitmap->getAddr8(0, 0),
343        static_cast<int>(input_bitmap->rowBytes()),
344        0, input_bitmap->bytesPerPixel(),
345        gradient_filter,
346        image_size,
347        intermediate2.getAddr8(0, 0),
348        static_cast<int>(intermediate2.rowBytes()),
349        0, intermediate2.bytesPerPixel(), true);
350  }
351
352  unsigned grad_max = 0;
353  for (int r = 0; r < image_size.height(); ++r) {
354    const uint8* grad_x_row = intermediate.getAddr8(0, r);
355    const uint8* grad_y_row = intermediate2.getAddr8(0, r);
356    for (int c = 0; c < image_size.width(); ++c) {
357      unsigned grad_x = grad_x_row[c];
358      unsigned grad_y = grad_y_row[c];
359      grad_max = std::max(grad_max, grad_x * grad_x + grad_y * grad_y);
360    }
361  }
362
363  int bit_shift = 0;
364  if (grad_max > 255)
365    bit_shift = static_cast<int>(
366        std::log10(static_cast<float>(grad_max)) / std::log10(2.0f)) - 7;
367  for (int r = 0; r < image_size.height(); ++r) {
368    const uint8* grad_x_row = intermediate.getAddr8(0, r);
369    const uint8* grad_y_row = intermediate2.getAddr8(0, r);
370    uint8* target_row = input_bitmap->getAddr8(0, r);
371    for (int c = 0; c < image_size.width(); ++c) {
372      unsigned grad_x = grad_x_row[c];
373      unsigned grad_y = grad_y_row[c];
374      target_row[c] = (grad_x * grad_x + grad_y * grad_y) >> bit_shift;
375    }
376  }
377}
378
379void ExtractImageProfileInformation(const SkBitmap& input_bitmap,
380                                    const gfx::Rect& area,
381                                    const gfx::Size& target_size,
382                                    bool apply_log,
383                                    std::vector<float>* rows,
384                                    std::vector<float>* columns) {
385  SkAutoLockPixels source_lock(input_bitmap);
386  DCHECK(rows);
387  DCHECK(columns);
388  DCHECK(input_bitmap.getPixels());
389  DCHECK_EQ(SkBitmap::kA8_Config, input_bitmap.config());
390  DCHECK_GE(area.x(), 0);
391  DCHECK_GE(area.y(), 0);
392  DCHECK_LE(area.right(), input_bitmap.width());
393  DCHECK_LE(area.bottom(), input_bitmap.height());
394
395  // Make sure rows and columns are allocated and initialized to 0.
396  rows->clear();
397  columns->clear();
398  rows->resize(area.height(), 0);
399  columns->resize(area.width(), 0);
400
401  for (int r = 0; r < area.height(); ++r) {
402    // Points to the first byte of the row in the rectangle.
403    const uint8* image_row = input_bitmap.getAddr8(area.x(), r + area.y());
404    unsigned row_sum = 0;
405    for (int c = 0; c < area.width(); ++c, ++image_row) {
406      row_sum += *image_row;
407      (*columns)[c] += *image_row;
408    }
409    (*rows)[r] = row_sum;
410  }
411
412  if (apply_log) {
413    // Generally for processing we will need to take logarithm of this data.
414    // The option not to apply it is left principally as a test seam.
415    std::vector<float>::iterator it;
416    for (it = columns->begin(); it < columns->end(); ++it)
417      *it = std::log(1.0f + *it);
418
419    for (it = rows->begin(); it < rows->end(); ++it)
420      *it = std::log(1.0f + *it);
421  }
422
423  if (!target_size.IsEmpty()) {
424    // If the target size is given, profiles should be further processed through
425    // morphological closing. The idea is to close valleys smaller than what
426    // can be seen after scaling down to avoid deforming noticable features
427    // when profiles are used.
428    // Morphological closing is defined as dilation followed by errosion. In
429    // normal-speak: sliding-window maximum followed by minimum.
430    int column_window_size = 1 + 2 *
431        static_cast<int>(0.5f * area.width() / target_size.width() + 0.5f);
432    int row_window_size = 1 + 2 *
433        static_cast<int>(0.5f * area.height() / target_size.height() + 0.5f);
434
435    // Dilate and erode each profile with the given window size.
436    if (column_window_size >= 3) {
437      SlidingWindowMinMax(columns->begin(),
438                          columns->end(),
439                          columns->begin(),
440                          column_window_size,
441                          std::greater<float>());
442      SlidingWindowMinMax(columns->begin(),
443                          columns->end(),
444                          columns->begin(),
445                          column_window_size,
446                          std::less<float>());
447    }
448
449    if (row_window_size >= 3) {
450      SlidingWindowMinMax(rows->begin(),
451                          rows->end(),
452                          rows->begin(),
453                          row_window_size,
454                          std::greater<float>());
455      SlidingWindowMinMax(rows->begin(),
456                          rows->end(),
457                          rows->begin(),
458                          row_window_size,
459                          std::less<float>());
460    }
461  }
462}
463
464float AutoSegmentPeaks(const std::vector<float>& input) {
465  // This is a thresholding operation based on Otsu's method.
466  std::vector<int> histogram;
467  std::pair<float, float> minmax;
468  if (!ComputeScaledHistogram(input, &histogram, &minmax))
469    return minmax.first;
470
471  // max_index refers to the bin *after* which we need to split. The sought
472  // threshold is the centre of this bin, scaled back to the original range.
473  size_t max_index = FindOtsuThresholdingIndex(histogram);
474  return (minmax.second - minmax.first) * (max_index + 0.5f) / 255.0f +
475      minmax.first;
476}
477
478gfx::Size AdjustClippingSizeToAspectRatio(const gfx::Size& target_size,
479                                          const gfx::Size& image_size,
480                                          const gfx::Size& computed_size) {
481  DCHECK_GT(target_size.width(), 0);
482  DCHECK_GT(target_size.height(), 0);
483  // If the computed thumbnail would be too wide or to tall, we shall attempt
484  // to fix it. Generally the idea is to re-add content to the part which has
485  // been more aggressively shrunk unless there is nothing to add there or if
486  // adding there won't fix anything. Should that be the case,  we will
487  // (reluctantly) take away more from the other dimension.
488  float desired_aspect =
489      static_cast<float>(target_size.width()) / target_size.height();
490  int computed_width = std::max(computed_size.width(), target_size.width());
491  int computed_height = std::max(computed_size.height(), target_size.height());
492  float computed_aspect = static_cast<float>(computed_width) / computed_height;
493  float aspect_change_delta = std::abs(computed_aspect - desired_aspect);
494  float prev_aspect_change_delta = 1000.0f;
495  const float kAspectChangeEps = 0.01f;
496  const float kLargeEffect = 2.0f;
497
498  while ((prev_aspect_change_delta - aspect_change_delta > kAspectChangeEps) &&
499         (computed_aspect / desired_aspect > kAspectRatioToleranceFactor ||
500          desired_aspect / computed_aspect > kAspectRatioToleranceFactor)) {
501    int new_computed_width = computed_width;
502    int new_computed_height = computed_height;
503    float row_dimension_shrink =
504        static_cast<float>(image_size.height()) / computed_height;
505    float column_dimension_shrink =
506        static_cast<float>(image_size.width()) / computed_width;
507
508    if (computed_aspect / desired_aspect > kAspectRatioToleranceFactor) {
509      // Too wide.
510      if (row_dimension_shrink > column_dimension_shrink) {
511        // Bring the computed_height to the least of:
512        // (1) image height (2) the number of lines that would
513        // make up the desired aspect or (3) number of lines we would get
514        // at the same 'aggressivity' level as width or.
515        new_computed_height = std::min(
516            static_cast<int>(image_size.height()),
517            static_cast<int>(computed_width / desired_aspect + 0.5f));
518        new_computed_height = std::min(
519            new_computed_height,
520            static_cast<int>(
521                image_size.height() / column_dimension_shrink + 0.5f));
522      } else if (row_dimension_shrink >= kLargeEffect ||
523                 new_computed_width <= target_size.width()) {
524        // Even though rows were resized less, we will generally rather add than
525        // remove (or there is nothing to remove in x already).
526        new_computed_height = std::min(
527            static_cast<int>(image_size.height()),
528            static_cast<int>(computed_width / desired_aspect + 0.5f));
529      } else {
530        // Rows were already shrunk less aggressively. This means there is
531        // simply no room left too expand. Cut columns to get the desired
532        // aspect ratio.
533        new_computed_width = desired_aspect * computed_height + 0.5f;
534      }
535    } else {
536      // Too tall.
537      if (column_dimension_shrink > row_dimension_shrink) {
538        // Columns were shrunk more aggressively. Try to relax the same way as
539        // above.
540        new_computed_width = std::min(
541            static_cast<int>(image_size.width()),
542            static_cast<int>(desired_aspect * computed_height + 0.5f));
543        new_computed_width = std::min(
544            new_computed_width,
545            static_cast<int>(
546                image_size.width() / row_dimension_shrink  + 0.5f));
547      } else if (column_dimension_shrink  >= kLargeEffect ||
548                 new_computed_height <= target_size.height()) {
549        new_computed_width = std::min(
550            static_cast<int>(image_size.width()),
551            static_cast<int>(desired_aspect * computed_height + 0.5f));
552      } else {
553        new_computed_height = computed_width / desired_aspect + 0.5f;
554      }
555    }
556
557    new_computed_width = std::max(new_computed_width, target_size.width());
558    new_computed_height = std::max(new_computed_height, target_size.height());
559
560    // Update loop control variables.
561    float new_computed_aspect =
562        static_cast<float>(new_computed_width) / new_computed_height;
563
564    if (std::abs(new_computed_aspect - desired_aspect) >
565        std::abs(computed_aspect - desired_aspect)) {
566      // Do not take inferior results.
567      break;
568    }
569
570    computed_width = new_computed_width;
571    computed_height = new_computed_height;
572    computed_aspect = new_computed_aspect;
573    prev_aspect_change_delta = aspect_change_delta;
574    aspect_change_delta = std::abs(new_computed_aspect - desired_aspect);
575  }
576
577  return gfx::Size(computed_width, computed_height);
578}
579
580void ConstrainedProfileSegmentation(const std::vector<float>& row_profile,
581                                    const std::vector<float>& column_profile,
582                                    const gfx::Size& target_size,
583                                    std::vector<bool>* included_rows,
584                                    std::vector<bool>* included_columns) {
585  DCHECK(included_rows);
586  DCHECK(included_columns);
587
588  std::vector<int> histogram_rows;
589  std::pair<float, float> minmax_rows;
590  bool rows_well_behaved = ComputeScaledHistogram(
591      row_profile, &histogram_rows, &minmax_rows);
592
593  float row_threshold = minmax_rows.first;
594  size_t clip_index_rows = 0;
595
596  if (rows_well_behaved) {
597    clip_index_rows = FindOtsuThresholdingIndex(histogram_rows);
598    row_threshold = (minmax_rows.second - minmax_rows.first) *
599        (clip_index_rows + 0.5f) / 255.0f + minmax_rows.first;
600  }
601
602  std::vector<int> histogram_columns;
603  std::pair<float, float> minmax_columns;
604  bool columns_well_behaved = ComputeScaledHistogram(column_profile,
605                                                     &histogram_columns,
606                                                     &minmax_columns);
607  float column_threshold = minmax_columns.first;
608  size_t clip_index_columns = 0;
609
610  if (columns_well_behaved) {
611    clip_index_columns = FindOtsuThresholdingIndex(histogram_columns);
612    column_threshold = (minmax_columns.second - minmax_columns.first) *
613        (clip_index_columns + 0.5f) / 255.0f + minmax_columns.first;
614  }
615
616  int auto_segmented_width = count_if(
617      column_profile.begin(), column_profile.end(),
618      std::bind2nd(std::greater<float>(), column_threshold));
619  int auto_segmented_height = count_if(
620      row_profile.begin(), row_profile.end(),
621      std::bind2nd(std::greater<float>(), row_threshold));
622
623  gfx::Size computed_size = AdjustClippingSizeToAspectRatio(
624      target_size,
625      gfx::Size(column_profile.size(), row_profile.size()),
626      gfx::Size(auto_segmented_width, auto_segmented_height));
627
628  // Apply thresholding.
629  if (rows_well_behaved) {
630    ConstrainedProfileThresholding(row_profile,
631                                   histogram_rows,
632                                   clip_index_rows,
633                                   row_threshold,
634                                   minmax_rows,
635                                   auto_segmented_height,
636                                   computed_size.height(),
637                                   included_rows);
638  } else {
639    // This is essentially an error condition, invoked when no segmentation was
640    // possible. This will result in applying a very low threshold and likely
641    // in producing a thumbnail which should get rejected.
642    included_rows->resize(row_profile.size());
643    for (size_t i = 0; i < row_profile.size(); ++i)
644      (*included_rows)[i] = row_profile[i] > row_threshold;
645  }
646
647  if (columns_well_behaved) {
648    ConstrainedProfileThresholding(column_profile,
649                                   histogram_columns,
650                                   clip_index_columns,
651                                   column_threshold,
652                                   minmax_columns,
653                                   auto_segmented_width,
654                                   computed_size.width(),
655                                   included_columns);
656  } else {
657    included_columns->resize(column_profile.size());
658    for (size_t i = 0; i < column_profile.size(); ++i)
659      (*included_columns)[i] = column_profile[i] > column_threshold;
660  }
661}
662
663SkBitmap ComputeDecimatedImage(const SkBitmap& bitmap,
664                               const std::vector<bool>& rows,
665                               const std::vector<bool>& columns) {
666  SkAutoLockPixels source_lock(bitmap);
667  DCHECK(bitmap.getPixels());
668  DCHECK_GT(bitmap.bytesPerPixel(), 0);
669  DCHECK_EQ(bitmap.width(), static_cast<int>(columns.size()));
670  DCHECK_EQ(bitmap.height(), static_cast<int>(rows.size()));
671
672  unsigned target_row_count = std::count(rows.begin(), rows.end(), true);
673  unsigned target_column_count = std::count(
674      columns.begin(), columns.end(), true);
675
676  if (target_row_count == 0 || target_column_count == 0)
677    return SkBitmap();  // Not quite an error, so no DCHECK. Just return empty.
678
679  if (target_row_count == rows.size() && target_column_count == columns.size())
680    return SkBitmap();  // Equivalent of the situation above (empty target).
681
682  // Allocate the target image.
683  SkBitmap target;
684  target.setConfig(bitmap.config(), target_column_count, target_row_count);
685  target.allocPixels();
686
687  int target_row = 0;
688  for (int r = 0; r < bitmap.height(); ++r) {
689    if (!rows[r])
690      continue;  // We can just skip this one.
691    uint8* src_row =
692        static_cast<uint8*>(bitmap.getPixels()) + r * bitmap.rowBytes();
693    uint8* insertion_target = static_cast<uint8*>(target.getPixels()) +
694        target_row * target.rowBytes();
695    int left_copy_pixel = -1;
696    for (int c = 0; c < bitmap.width(); ++c) {
697      if (left_copy_pixel < 0 && columns[c]) {
698        left_copy_pixel = c;  // Next time we will start copying from here.
699      } else if (left_copy_pixel >= 0 && !columns[c]) {
700        // This closes a fragment we want to copy. We do it now.
701        size_t bytes_to_copy = (c - left_copy_pixel) * bitmap.bytesPerPixel();
702        memcpy(insertion_target,
703               src_row + left_copy_pixel * bitmap.bytesPerPixel(),
704               bytes_to_copy);
705        left_copy_pixel = -1;
706        insertion_target += bytes_to_copy;
707      }
708    }
709    // We can still have the tail end to process here.
710    if (left_copy_pixel >= 0) {
711      size_t bytes_to_copy =
712          (bitmap.width() - left_copy_pixel) * bitmap.bytesPerPixel();
713      memcpy(insertion_target,
714             src_row + left_copy_pixel * bitmap.bytesPerPixel(),
715             bytes_to_copy);
716    }
717    target_row++;
718  }
719
720  return target;
721}
722
723SkBitmap CreateRetargetedThumbnailImage(
724    const SkBitmap& source_bitmap,
725    const gfx::Size& target_size,
726    float kernel_sigma) {
727  // First thing we need for this method is to color-reduce the source_bitmap.
728  SkBitmap reduced_color;
729  reduced_color.setConfig(
730      SkBitmap::kA8_Config, source_bitmap.width(), source_bitmap.height());
731  reduced_color.allocPixels();
732
733  if (!color_utils::ComputePrincipalComponentImage(source_bitmap,
734                                                   &reduced_color)) {
735    // CCIR601 luminance conversion vector.
736    gfx::Vector3dF transform(0.299f, 0.587f, 0.114f);
737    if (!color_utils::ApplyColorReduction(
738            source_bitmap, transform, true, &reduced_color)) {
739      DLOG(WARNING) << "Failed to compute luminance image from a screenshot. "
740                    << "Cannot compute retargeted thumbnail.";
741      return SkBitmap();
742    }
743    DLOG(WARNING) << "Could not compute principal color image for a thumbnail. "
744                  << "Using luminance instead.";
745  }
746
747  // Turn 'color-reduced' image into the 'energy' image.
748  ApplyGaussianGradientMagnitudeFilter(&reduced_color, kernel_sigma);
749
750  // Extract vertical and horizontal projection of image features.
751  std::vector<float> row_profile;
752  std::vector<float> column_profile;
753  ExtractImageProfileInformation(reduced_color,
754                                 gfx::Rect(reduced_color.width(),
755                                           reduced_color.height()),
756                                 target_size,
757                                 true,
758                                 &row_profile,
759                                 &column_profile);
760
761  std::vector<bool> included_rows, included_columns;
762  ConstrainedProfileSegmentation(row_profile,
763                                 column_profile,
764                                 target_size,
765                                 &included_rows,
766                                 &included_columns);
767
768  // Use the original image and computed inclusion vectors to create a resized
769  // image.
770  return ComputeDecimatedImage(source_bitmap, included_rows, included_columns);
771}
772
773}  // thumbnailing_utils
774