| /* |
| * Copyright 2014 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| // Author: Huibao Lin |
| |
| #include "pagespeed/kernel/image/image_analysis.h" |
| |
| #include <stdbool.h> |
| #include <algorithm> |
| #include <cmath> |
| #include <cstdlib> |
| #include "base/logging.h" |
| #include "pagespeed/kernel/base/scoped_ptr.h" |
| #include "pagespeed/kernel/base/string.h" |
| #include "pagespeed/kernel/image/image_frame_interface.h" |
| #include "pagespeed/kernel/image/jpeg_utils.h" |
| #include "pagespeed/kernel/image/pixel_format_optimizer.h" |
| #include "pagespeed/kernel/image/read_image.h" |
| #include "pagespeed/kernel/image/scanline_interface.h" |
| #include "pagespeed/kernel/image/scanline_interface_frame_adapter.h" |
| #include "pagespeed/kernel/image/scanline_status.h" |
| #include "pagespeed/kernel/image/scanline_utils.h" |
| |
| namespace pagespeed { |
| |
| namespace { |
| |
| // Threshold for histogram. The histogram bins with values less than |
| // (max_hist_bin * kHistogramThreshold) will be ignored in computing |
| // the photo metric. Values of 0.005, 0.01, and 0.02 have been tried and |
| // the best one is 0.01. |
| const float kHistogramThreshold = 0.01; |
| |
| // Minimum metric value in order to be treated as a photo. The recommended |
| // value, 16, was found by examining about 1000 PNG images with no alpha |
| // or a completely opaque alpha channel. |
| const float kPhotoMetricThreshold = 16; |
| |
| template <class T> |
| inline T AbsDif(T v1, T v2) { |
| return (v1 >= v2 ? v1 - v2 : v2 - v1); |
| } |
| |
| } // namespace |
| |
| namespace image_compression { |
| |
| // Compute the gradient by Sobel filter. The kernels in the x and y |
| // directions, respectively, are given by: |
| // [ 1 2 1 ] [ 1 0 -1 ] |
| // [ 0 0 0 ] [ 2 0 -2 ] |
| // [ -1 -2 -1 ] [ 1 0 -1 ] |
| template<class T> |
| void ComputeGradientFromLuminance(const T* luminance, int width, int height, |
| int elements_per_line, float norm_factor, |
| uint8_t* gradient) { |
| memset(gradient, 0, width * height * sizeof(gradient[0])); |
| norm_factor *= 0.25; // Remove the magnification factor of Sobel filter (4). |
| for (int y = 1; y < height - 1; ++y) { |
| int in_idx = y * elements_per_line + 1; |
| int out_idx = y * width + 1; |
| for (int x = 1; x < width - 1; ++x, ++in_idx, ++out_idx) { |
| int32_t dif_y = |
| static_cast<int32_t>(luminance[in_idx - elements_per_line - 1]) + |
| (static_cast<int32_t>(luminance[in_idx - elements_per_line]) << 1) + |
| static_cast<int32_t>(luminance[in_idx - elements_per_line + 1]) - |
| static_cast<int32_t>(luminance[in_idx + elements_per_line - 1]) - |
| (static_cast<int32_t>(luminance[in_idx + elements_per_line]) << 1) - |
| static_cast<int32_t>(luminance[in_idx + elements_per_line + 1]); |
| |
| int32_t dif_x = |
| static_cast<int32_t>(luminance[in_idx - 1 - elements_per_line]) + |
| (static_cast<int32_t>(luminance[in_idx - 1]) << 1) + |
| static_cast<int32_t>(luminance[in_idx - 1 + elements_per_line]) - |
| static_cast<int32_t>(luminance[in_idx + 1 - elements_per_line]) - |
| (static_cast<int32_t>(luminance[in_idx + 1]) << 1) - |
| static_cast<int32_t>(luminance[in_idx + 1 + elements_per_line]); |
| |
| // The results of "dif_x * dif_x + dif_y * dif_y" will not overflow |
| // because the data in dif_x and dif_y have at most 12 bits. |
| float dif2 = static_cast<float>(dif_x * dif_x + dif_y * dif_y); |
| float dif = std::sqrt(dif2) * norm_factor + 0.5f; |
| gradient[out_idx] = static_cast<uint8_t>(std::min(255.0f, dif)); |
| } |
| } |
| } |
| |
| bool SobelGradient(const uint8_t* image, int width, int height, |
| int bytes_per_line, PixelFormat pixel_format, |
| MessageHandler* handler, uint8_t* gradient) { |
| if (width < 3 || height < 3 || |
| (pixel_format != GRAY_8 && pixel_format != RGB_888 && |
| pixel_format != RGBA_8888)) { |
| return false; |
| } |
| |
| if (pixel_format == GRAY_8) { |
| const float norm_factor = 1.0f; |
| ComputeGradientFromLuminance(image, width, height, bytes_per_line, |
| norm_factor, gradient); |
| } else { |
| int32_t* luminance = static_cast<int32_t*>(malloc(width * height * |
| sizeof(int32_t))); |
| if (luminance == NULL) { |
| return false; |
| } |
| |
| const int num_channels = |
| GetNumChannelsFromPixelFormat(pixel_format, handler); |
| |
| // Compute the luminance which is simply the average of R, G, and B |
| // after applying the normalization factor. |
| int32_t* out_pixel = luminance; |
| for (int y = 0; y < height; ++y) { |
| const uint8_t* in_channel = image + y * bytes_per_line; |
| for (int x = 0; x < width; ++x) { |
| *out_pixel = static_cast<int32_t>(in_channel[0]) + |
| static_cast<int32_t>(in_channel[1]) + |
| static_cast<int32_t>(in_channel[2]); |
| ++out_pixel; |
| in_channel += num_channels; |
| } |
| } |
| |
| const float norm_factor = 1.0f / 3.0f; |
| ComputeGradientFromLuminance(luminance, width, height, width, norm_factor, |
| gradient); |
| free(luminance); |
| } |
| return true; |
| } |
| |
| void Histogram(const uint8_t* image, int width, int height, int bytes_per_line, |
| int x0, int y0, float* hist) { |
| DCHECK(bytes_per_line >= width); |
| |
| uint32_t hist_int[kNumColorHistogramBins]; |
| memset(hist_int, 0, kNumColorHistogramBins * sizeof(hist_int[0])); |
| |
| // Aggregate the histogram. |
| for (int y = y0; y < y0 + height; ++y) { |
| int i = y * bytes_per_line + x0; |
| for (int x = 0; x < width; ++x, ++i) { |
| ++hist_int[image[i]]; |
| } |
| } |
| |
| for (int i = 0; i < kNumColorHistogramBins; ++i) { |
| hist[i] = static_cast<float>(hist_int[i]); |
| } |
| } |
| |
| float WidestPeakWidth(const float* hist, float threshold) { |
| float max_hist = *std::max_element(hist, hist + kNumColorHistogramBins); |
| float threshold_hist = threshold * max_hist; |
| |
| int widest_peak = 0; |
| int i = 0; |
| while (i < kNumColorHistogramBins) { |
| // Skip all bins which are smaller than the threshold. |
| for (; i < kNumColorHistogramBins && hist[i] < threshold_hist; ++i) { |
| } |
| // Now we have a bin which meets the threshold, or we have finished |
| // all of the bins. |
| int first_significant_bin = i; |
| for (; i < kNumColorHistogramBins && hist[i] >= threshold_hist; ++i) { |
| } |
| // Now we have gone through a peak or we have run out of bins. We will |
| // check whether it is wider than all of the previous ones. |
| float width = i - first_significant_bin; |
| if (widest_peak < width) { |
| widest_peak = width; |
| } |
| } |
| |
| return widest_peak; |
| } |
| |
| float PhotoMetric(const uint8_t* image, int width, int height, |
| int bytes_per_line, PixelFormat pixel_format, |
| float threshold, MessageHandler* handler) { |
| const float KMinMetric = 0; |
| |
| uint8_t* gradient = static_cast<uint8_t*>(malloc(width * height * |
| sizeof(uint8_t))); |
| if (gradient == NULL) { |
| return KMinMetric; |
| } |
| |
| if (!SobelGradient(image, width, height, bytes_per_line, pixel_format, |
| handler, gradient)) { |
| // Conservatively assume that the image is computer generated graphics if we |
| // cannot compute its gradient. |
| free(gradient); |
| return KMinMetric; |
| } |
| |
| float hist[kNumColorHistogramBins]; |
| Histogram(gradient, width-2, height-2, width, 1, 1, hist); |
| free(gradient); |
| return WidestPeakWidth(hist, threshold); |
| } |
| |
| bool IsPhoto(ScanlineReaderInterface* reader, MessageHandler* handler) { |
| // Pretend that the image is not a photo if we cannot process it. |
| bool kDefaultReturnValue = false; |
| |
| // If we cannot process the image or if the image has non-opaque alpha |
| // channel, return false (i.e., not a photo). Most (>99%) images with |
| // non-opaque alpha channel are not photo. |
| if (reader->GetPixelFormat() == UNSUPPORTED || |
| reader->GetPixelFormat() == RGBA_8888 || |
| reader->GetImageWidth() == 0 || reader->GetImageHeight() == 0) { |
| return kDefaultReturnValue; |
| } |
| |
| const int width = reader->GetImageWidth(); |
| const int height = reader->GetImageHeight(); |
| const PixelFormat pixel_format = reader->GetPixelFormat(); |
| const int bytes_per_line = width * |
| GetNumChannelsFromPixelFormat(pixel_format, handler); |
| |
| uint8_t* image = static_cast<uint8_t*>(malloc(bytes_per_line * height * |
| sizeof(uint8_t))); |
| if (image == NULL) { |
| return kDefaultReturnValue; |
| } |
| |
| for (int y = 0; y < height; ++y) { |
| uint8_t* scanline = NULL; |
| if (!reader->HasMoreScanLines() || |
| !reader->ReadNextScanline(reinterpret_cast<void**>(&scanline))) { |
| free(image); |
| return kDefaultReturnValue; |
| } |
| memcpy(image + y * bytes_per_line, scanline, bytes_per_line); |
| } |
| |
| float metric = PhotoMetric(image, width, height, bytes_per_line, |
| pixel_format, kHistogramThreshold, handler); |
| free(image); |
| return metric >= kPhotoMetricThreshold; |
| } |
| |
| bool AnalyzeImage(ImageFormat image_type, |
| const void* image_buffer, |
| size_t buffer_length, |
| int* width, |
| int* height, |
| bool* is_progressive, |
| bool* is_animated, |
| bool* has_transparency, |
| bool* is_photo, |
| int* quality, |
| ScanlineReaderInterface** reader, |
| MessageHandler* handler) { |
| net_instaweb::scoped_ptr<ScanlineReaderInterface> sf_reader; |
| net_instaweb::scoped_ptr<PixelFormatOptimizer> optimizer; |
| bool image_is_animated = false; |
| int image_width = 0; |
| int image_height = 0; |
| bool image_is_progressive = false; |
| ScanlineStatus status; |
| if (image_type != IMAGE_GIF) { |
| // PNG and JPEG images only have a single frame. WebP may have multiple |
| // frames but that is rare, so they will not be analyzed. |
| |
| // TODO(huibao): Upgrade WebpScanlineReader to support multiple frame |
| // WebP images. |
| sf_reader.reset(CreateScanlineReader(image_type, image_buffer, |
| buffer_length, handler)); |
| if (sf_reader == NULL) { |
| return false; |
| } |
| } else { |
| // GIF images may have multiple frames (animation). If it has multiple |
| // frames, we can only get its width and height; if not, we can convert |
| // it to a scanline reader and find out whether it is a photo and/or |
| // transparent. |
| net_instaweb::scoped_ptr<MultipleFrameReader> mf_reader( |
| CreateImageFrameReader(image_type, image_buffer, buffer_length, |
| handler, &status)); |
| if (mf_reader == NULL) { |
| return false; |
| } |
| |
| ImageSpec image_spec; |
| if (!mf_reader->GetImageSpec(&image_spec, &status)) { |
| return false; |
| } |
| image_is_animated = (image_spec.num_frames > 1); |
| |
| if (image_is_animated) { |
| image_width = image_spec.width; |
| image_height = image_spec.height; |
| } else { |
| sf_reader.reset(new FrameToScanlineReaderAdapter(mf_reader.release())); |
| if (sf_reader == NULL) { |
| return false; |
| } |
| status = sf_reader->InitializeWithStatus(image_buffer, buffer_length); |
| if (!status.Success()) { |
| return false; |
| } |
| } |
| } |
| |
| if (!image_is_animated) { |
| image_width = sf_reader->GetImageWidth(); |
| image_height = sf_reader->GetImageHeight(); |
| image_is_progressive = sf_reader->IsProgressive(); |
| } |
| |
| // No matter how many frames the image has, we can always find out whether it |
| // is animated, its width, and its height. |
| if (is_animated != NULL) { |
| *is_animated = image_is_animated; |
| } |
| if (width != NULL) { |
| *width = image_width; |
| } |
| if (height != NULL) { |
| *height = image_height; |
| } |
| if (is_progressive != NULL) { |
| *is_progressive = image_is_progressive; |
| } |
| |
| // Finding whether the image is transparent or photo requires processing |
| // the entire image. We do this only when it's requested. We also do this |
| // only for single frame images now, because for mutliple frames images each |
| // frame may have different attributes. |
| // |
| // TODO(huibao): Enhance PixelFormatOptimizer and IsPhoto() so they support |
| // MultipleFrameReader. PixelFormatOptimizer may return unique attributes |
| // for each frame since the frames may have different values. IsPhoto() may |
| // return a single value for all of the frames because it is unlikely that |
| // the image consists of both photos and graphics. |
| if (sf_reader != NULL && (has_transparency != NULL || is_photo != NULL)) { |
| // Initialize the optimizer which will remove alpha channel if it is |
| // completely opaque. |
| optimizer.reset(new PixelFormatOptimizer(handler)); |
| if (!optimizer->Initialize(sf_reader.release()).Success()) { |
| return false; |
| } |
| |
| // Report the interesting information of the optimized image. |
| if (has_transparency != NULL) { |
| *has_transparency = (optimizer->GetPixelFormat() == RGBA_8888); |
| } |
| if (is_photo != NULL) { |
| if (image_type == IMAGE_JPEG) { |
| // Assume all JPEG images are photos. JPEG is the most popular format |
| // in internet and most of them have photo content. For the very few |
| // JPEG image with graphics content, we can't really improve the quality |
| // by losslessly encoding them, so we simply assume all of them to |
| // be photos, in order to save computations. |
| *is_photo = true; |
| } else { |
| // IsPhoto will read all scanlines of the image, so optimizer cannot be |
| // used anymore. |
| *is_photo = IsPhoto(optimizer.get(), handler); |
| optimizer.reset(); |
| } |
| } |
| } |
| |
| if (quality != NULL && image_type == IMAGE_JPEG) { |
| *quality = JpegUtils::GetImageQualityFromImage(image_buffer, buffer_length, |
| handler); |
| // TODO(huibao): Add utility for finding quality number from WebP images |
| // and apply it here. |
| } |
| |
| // If "reader" has been requested, the caller is responsible for destroying |
| // it. |
| if (reader != NULL) { |
| if (optimizer != NULL) { |
| *reader = optimizer.release(); |
| } else if (sf_reader != NULL) { |
| *reader = sf_reader.release(); |
| } else { |
| *reader = NULL; |
| } |
| } |
| |
| return true; |
| } |
| |
| } // namespace image_compression |
| |
| } // namespace pagespeed |