00、背景

Google图片搜索是Google公司于2001年7月推出的图片搜索服务。

Google总裁Eric Schmidt表示，Google图片的建立，是因为他想要看"珍妮弗·洛佩兹的绿色范思哲礼服"。

2001年，Google图片编入了2.5亿张图片。2005年，这一数字增长到了十亿。到了2010年，已可搜索100亿张图片。截至2010年7月，该服务每天被访问超过一亿次。

01、感知哈希（Perceptual hashing ）

感知哈希是使用指纹算法生成各种形式的多媒体的片段、哈希或指纹。

感知哈希是一种位置敏感哈希，如果多媒体的特征相似，则它是类似的。

这与加密哈希相反，加密哈希依赖于输入值的微小变化造成输出值的巨大变化的雪崩效应。

感知散列函数广泛用于查找在线版权侵权案件以及数字取证，因为散列之间具有相关性，因此可以找到相似的数据（例如具有不同的水印）。

它是基于DCT（离散余弦变换）来得到图片的hash值，具体步骤如下：

1、缩小图片：32*32是一个较好的大小，这样方便DCT计算；

2、灰度化：转换为256阶灰度图；

3、计算DCT：DCT把图片分离成分率的集合，DCT（离散余弦变换）；

4、缩小DCT：DCT计算后的矩阵是32 * 32，保留左上角的8 * 8，这些代表的图片的最低频率；

5、计算平均值：计算缩小DCT后的所有像素点的平均值；

6、比较平均值：大于平均值记录为1，反之记录为0，得到phash值。

02、发展历史

Marr 和 Hildreth 1980 年的工作是该领域的开创性论文。

Christoph Zauner 2010 年 7 月的论文对该主题进行了精彩的介绍。

2016 年 6 月，Azadeh Amir Asgari 发表了有关鲁棒图像哈希欺骗的研究成果。Asgari 指出，感知哈希函数像任何其他算法一样容易出错。

研究人员在 2017 年 12 月表示，谷歌图像搜索基于感知哈希。

PHA是一类比较哈希方法的统称。图片所包含的特征被用来生成一组指纹（不过它不是唯一的）,而这些指纹是可以进行比较的。

这个算法非常巧妙，无论你改变图片的高宽、亮度甚至颜色，都不会改变哈希值。

03、实现示意

04、核心代码

使用差分哈希算法计算图像的64位哈希

  /// <summary>
  /// 使用差分哈希算法计算图像的64位哈希。
  /// </summary>
  /// <param name="image">读取到的图片流</param>
  /// <returns>256位hash值</returns>
  public ulong[] DifferenceHash256(Image<Rgba32> image)
  {
      var pixels = _transformer.TransformImage(image, 17, 16);

      // 遍历像素，如果左侧像素比右侧像素亮，则将哈希设置为1。
      var hash = new ulong[4];
      var hashPos = 0;
      var hashPart = 0;
      for (var i = 0; i < 16; i++)
      {
          var rowStart = i * 17;
          for (var j = 0; j < 16; j++)
          {
              if (pixels[rowStart + j] > pixels[rowStart + j + 1])
              {
                  hash[hashPart] |= 1UL << hashPos;
              }

              if (hashPos == 63)
              {
                  hashPos = 0;
                  hashPart++;
              }
              else
              {
                  hashPos++;
              }
          }
      }

      return hash;
  }

构建索引

      private async void btnIndex_Click(object sender, EventArgs e)
      {
          if (IndexRunning)
          {
              IndexRunning = false;
              btnIndex.Text = "更新索引";
              return;
          }

          if (string.IsNullOrEmpty(txtDirectory.Text))
          {
              MessageBox.Show("请先选择文件夹");
              return;
          }

          IndexRunning = true;
          btnIndex.Text = "停止索引";
          cbRemoveInvalidIndex.Hide();
          var imageHasher = new ImageHasher(new ImageSharpTransformer());
          int? filesCount = null;
          Task.Run(() => filesCount = Directory.EnumerateFiles(txtDirectory.Text, "*", SearchOption.AllDirectories).Except(_index.Keys).Count(s => Regex.IsMatch(s, "(jpg|png|bmp)#34;, RegexOptions.IgnoreCase))).ConfigureAwait(false);
          var local = new ThreadLocal<int>(true);
          await Task.Run(() =>
          {
              var sw = Stopwatch.StartNew();
              long size = 0;
              Directory.EnumerateFiles(txtDirectory.Text, "*", SearchOption.AllDirectories).Except(_index.Keys).Where(s => Regex.IsMatch(s, "(jpg|png|bmp)#34;, RegexOptions.IgnoreCase)).Chunk(Environment.ProcessorCount * 2).AsParallel().WithDegreeOfParallelism(Environment.ProcessorCount * 2).ForAll(g =>
                {
                    foreach (var s in g)
                    {
                        if (IndexRunning)
                        {
                            if (lblProcess.InvokeRequired)
                            {
                                local.Value++;
                                lblProcess.Invoke(() => lblProcess.Text = #34;{local.Values.Sum()}/{filesCount}");
                            }
                            try
                            {
                                _index.GetOrAdd(s, _ => imageHasher.DifferenceHash256(s));
                                size += new FileInfo(s).Length;
                            }
                            catch
                            {
                                LogManager.Info(s + "格式不正确");
                            }
                        }
                        else
                        {
                            break;
                        }
                    }
                });
              lbSpeed.Text = #34;索引速度: {Math.Round(local.Values.Sum() * 1.0 / sw.Elapsed.TotalSeconds)} items/s({size * 1f / 1048576 / sw.Elapsed.TotalSeconds:N}MB/s)";
              if (cbRemoveInvalidIndex.Checked)
              {
                  foreach (var (key, _) in _index.AsParallel().WithDegreeOfParallelism(32).Where(s => !File.Exists(s.Key)))
                  {
                      _index.TryRemove(key, out _);
                  }
              }

              lbIndexCount.Text = _index.Count + "文件";
              cbRemoveInvalidIndex.Show();
              var json = JsonSerializer.Serialize(_index);
              File.WriteAllText("index.json", json, Encoding.UTF8);
              MessageBox.Show("索引创建完成，耗时：" + sw.Elapsed.TotalSeconds + "s");
          }).ConfigureAwait(false);
          IndexRunning = false;
          btnIndex.Text = "更新索引";
      }

索引结构如下：

05、最后效果

匹配度100%：

匹配度74.21%：