media/cast/test/utility/barcode.cc

   1 // Copyright 2014 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 // Routines for encoding and decoding a small number of bits into an image
   6 // in a way that is decodable even after scaling/encoding/cropping.
   7 //
   8 // The encoding is very simple:
   9 //
  10 //   ####    ####    ########    ####        ####    ####
  11 //   ####    ####    ########    ####        ####    ####
  12 //   ####    ####    ########    ####        ####    ####
  13 //   ####    ####    ########    ####        ####    ####
  14 //   1   2   3   4   5   6   7   8   9   10  11  12  13  14
  15 //   <-----start----><--one-bit-><-zero bit-><----stop---->
  16 //
  17 // We use a basic unit, depicted here as four characters wide.
  18 // We start with 1u black 1u white 1u black 1u white. (1-4 above)
  19 // From there on, a "one" bit is encoded as 2u black and 1u white,
  20 // and a zero bit is encoded as 1u black and 2u white. After
  21 // all the bits we end the pattern with the same pattern as the
  22 // start of the pattern.
  23
  24 #include <deque>
  25 #include <vector>
  26
  27 #include "base/logging.h"
  28 #include "media/base/video_frame.h"
  29 #include "media/cast/test/utility/barcode.h"
  30
  31 namespace media {
  32 namespace cast {
  33 namespace test {
  34
  35 const int kBlackThreshold = 256 * 2 / 3;
  36 const int kWhiteThreshold = 256 / 3;
  37
  38 bool EncodeBarcode(const std::vector<bool>& bits,
  39                    scoped_refptr<VideoFrame> output_frame) {
  40   DCHECK(output_frame->format() == VideoFrame::YV12 ||
  41          output_frame->format() == VideoFrame::YV16 ||
  42          output_frame->format() == VideoFrame::I420 ||
  43          output_frame->format() == VideoFrame::YV12J);
  44   int row_bytes = output_frame->row_bytes(VideoFrame::kYPlane);
  45   std::vector<unsigned char> bytes(row_bytes);
  46   for (int i = 0; i < row_bytes; i++) {
  47     bytes[i] = 255;
  48   }
  49   size_t units = bits.size() * 3 + 7;  // White or black bar where size matters.
  50   // We only use 60% of the image to make sure it works even if
  51   // the image gets cropped.
  52   size_t unit_size = row_bytes * 6 / 10 / units;
  53   if (unit_size < 1) return false;
  54   size_t bytes_required = unit_size * units;
  55   size_t padding = (row_bytes - bytes_required) / 2;
  56   unsigned char *pos = &bytes[padding];
  57   // Two leading black bars.
  58   memset(pos, 0, unit_size);
  59   pos += unit_size * 2;
  60   memset(pos, 0, unit_size);
  61   pos += unit_size * 2;
  62   for (size_t bit = 0; bit < bits.size(); bit++) {
  63     memset(pos, 0, bits[bit] ? unit_size * 2: unit_size);
  64     pos += unit_size * 3;
  65   }
  66   memset(pos, 0, unit_size);
  67   pos += unit_size * 2;
  68   memset(pos, 0, unit_size);
  69   pos += unit_size;
  70   DCHECK_LE(pos - &bytes.front(), row_bytes);
  71
  72   // Now replicate this one row into all rows in kYPlane.
  73   for (int row = 0; row < output_frame->rows(VideoFrame::kYPlane); row++) {
  74     memcpy(output_frame->data(VideoFrame::kYPlane) +
  75            output_frame->stride(VideoFrame::kYPlane) * row,
  76            &bytes.front(),
  77            row_bytes);
  78   }
  79   return true;
  80 }
  81
  82 namespace {
  83 bool DecodeBarCodeRows(const scoped_refptr<VideoFrame>& frame,
  84                        std::vector<bool>* output,
  85                        int min_row,
  86                        int max_row) {
  87   // Do a basic run-length encoding
  88   std::deque<int> runs;
  89   bool is_black = true;
  90   int length = 0;
  91   for (int pos = 0; pos < frame->row_bytes(VideoFrame::kYPlane); pos++) {
  92     float value = 0.0;
  93     for (int row = min_row; row < max_row; row++) {
  94       value += frame->data(VideoFrame::kYPlane)[
  95           frame->stride(VideoFrame::kYPlane) * row + pos];
  96     }
  97     value /= max_row - min_row;
  98     if (is_black ? value > kBlackThreshold : value < kWhiteThreshold) {
  99       is_black = !is_black;
 100       runs.push_back(length);
 101       length = 1;
 102     } else {
 103       length++;
 104     }
 105   }
 106   runs.push_back(length);
 107
 108   // Try decoding starting at each white-black transition.
 109   while (runs.size() >=  output->size() * 2 + 7) {
 110     std::deque<int>::const_iterator i = runs.begin();
 111     double unit_size = (i[1] + i[2] + i[3] + i[4]) / 4;
 112     bool valid = true;
 113     if (i[0] > unit_size * 2 || i[0] < unit_size / 2) valid = false;
 114     if (i[1] > unit_size * 2 || i[1] < unit_size / 2) valid = false;
 115     if (i[2] > unit_size * 2 || i[2] < unit_size / 2) valid = false;
 116     if (i[3] > unit_size * 2 || i[3] < unit_size / 2) valid = false;
 117     i += 4;
 118     for (size_t bit = 0; valid && bit < output->size(); bit++) {
 119       if (i[0] > unit_size / 2 && i[0] <= unit_size * 1.5 &&
 120           i[1] > unit_size * 1.5 && i[1] <= unit_size * 3) {
 121         (*output)[bit] = false;
 122       } else if (i[1] > unit_size / 2 && i[1] <= unit_size * 1.5 &&
 123                  i[0] > unit_size * 1.5 && i[0] <= unit_size * 3) {
 124         (*output)[bit] = true;
 125       } else {
 126         // Not a valid code
 127         valid = false;
 128       }
 129       i += 2;
 130     }
 131     if (i[0] > unit_size * 2 || i[0] < unit_size / 2) valid = false;
 132     if (i[1] > unit_size * 2 || i[1] < unit_size / 2) valid = false;
 133     if (i[2] > unit_size * 2 || i[2] < unit_size / 2) valid = false;
 134     i += 3;
 135     DCHECK(i <= runs.end());
 136     if (valid) {
 137       // Decoding successful, return true
 138      return true;
 139     }
 140     runs.pop_front();
 141     runs.pop_front();
 142   }
 143   return false;
 144 }
 145
 146 }  // namespace
 147
 148 // Note that "output" is assumed to be the right size already. This
 149 // could be inferred from the data, but the decoding is more robust
 150 // if we can assume that we know how many bits we want.
 151 bool DecodeBarcode(const scoped_refptr<VideoFrame>& frame,
 152                    std::vector<bool>* output) {
 153   DCHECK(frame->format() == VideoFrame::YV12 ||
 154          frame->format() == VideoFrame::YV16 ||
 155          frame->format() == VideoFrame::I420 ||
 156          frame->format() == VideoFrame::YV12J);
 157   int rows = frame->rows(VideoFrame::kYPlane);
 158   // Middle 10 lines
 159   if (DecodeBarCodeRows(frame,
 160                         output,
 161                         std::max(0, rows / 2 - 5),
 162                         std::min(rows, rows / 2 + 5))) {
 163     return true;
 164   }
 165
 166   // Top 5 lines
 167   if (DecodeBarCodeRows(frame, output, 0, std::min(5, rows))) {
 168     return true;
 169   }
 170
 171   return false;
 172 }
 173
 174 }  // namespace test
 175 }  // namespace cast
 176 }  // namespace media