【FCon】聚焦金融行业在数智化的全面革新,一线的金融数智化实践干货 了解详情
写点什么

图片相似度计算:深入理解 DCT 变换以及感知哈希

  • 2018-11-21
  • 本文字数:3376 字

    阅读完需:约 11 分钟

图片相似度计算:深入理解DCT变换以及感知哈希

6 月 17 日,极客时间《企业级 Agents 开发实战营》正式上线,10 周掌握企业级 Agents 从设计、开发到部署全流程。

缘起

Android 上硬件编解码一直是个老大难问题,就解码来说,硬解码本身并不困难,只要按照 MediaCodec 的流程开发即可。但由于系统碎片化,硬件规格不一致,硬件解码会到黑屏,花屏,绿屏之类的显示问题。为了不招致用户投诉,我们在做视频解码的时候不太敢开启硬件加速,一般会采用保守策略,即以软解为主,优先保证画面正常,但牺牲了性能。


一般解决这个问题的方案是使用黑(白)机型名单下发配置(如:腾讯视频),或者暴露开关让用户手动去控制是否走硬件解码(如:bilibili)。


使用机型黑(白)名单有一定的作用,但其问题也显而易见:


  • 需要浪费大量的人力,精力进行机型测试,去维护,发布名单

  • 覆盖度偏低,一般只覆盖 TOP 机型

  • 缺乏时效性,例如新机型上市不能及时跟进

  • 不一定准确,因为硬解是否成功,跟视频源也有很大关系,同一个机型可能解这个视频不成功,另外一个视频又是成功的。按照机型"一刀切"的前提是要保证视频规格一致,这样才最健壮。


通过开关让用户切换体验太差,尤其是“抖音”之类的短视频 App,总不能每个界面加个开关让用户去切换解码器这么深奥的东西吧,从用户角度讲,我为什么要关心这个什么解码器怎么设置,只要视频能正常看就行。


仔细思考一下,我们其实可以实现自动化的检测,即模拟人工检测流程,把样本视频各软硬解一遍,然后对比他们的解码结果(图片)就能够知道硬解码是否能跑通。解码的流程轻车熟路,那么这里的关键问题就是我们如何进行图片对比?如何量化图片的差异度?

图片检索技术

图片对比其实跟"以图搜图"本质上是同一种技术,通常有几种做法 MSE,均值哈希,色彩直方图以及 OpenCV 里面一些提取图像特征的高级算法,如 Sift,Surf 等。基于移动端的运行效率,安装包大小,以及需求本身考虑,我们放弃引入 OpenCV。MSE 属于逐像素对比,对像素值要求过于严格,太简单粗暴,色彩直方图不太好量化差异度。基于以上考虑,我们选择图像哈希算法,它可以输出汉明距离,方便量化软硬解结果的差异度。


哈希算法有三种,平均哈希,感知哈希和差异度哈希,基于准确度考虑,我们选择实现较复杂一些的感知哈希算法。另基于性能考虑,我们在 Android 平台上使用 C++实现算法,通过 JNI 接口给 Java 调用。Java 层输入 Android 的 Bitmap 对象,输出为图片指纹,再通过对比指纹的汉明距离,我们即可判断出来解码是否正常。


Java 层接口签名如下:


public native long getHash(Bitmap bitmap, int algorithm);public native long getHammingDistance(long hash1, long hash2);
复制代码


下面分析一下感知哈希实现的方法和背后的原理,使之知其然,知其所以然。

图片的构成


图一



图二


我们知道图片由 RGB 三原色构成这称之为加色法,我们可以认为图片有三个维度(暂不考虑 Alpha)。分析上面两幅图,图一为原图,可以发现图片里蕴含的大部分信息都是低频的,比如天空,绿叶,树枝等,他们很少变化。高频信息是小鸟的眼睛,嘴巴等细节。图二是把图一经过缩放且只保留亮度信息,可以看到这有效的移除了图片的细节,即高频信息,展示了图片的低频部分。图片的低频部分决定了图片的大体结构,高频部分则完善了图片的细节。我们在对比图片是否相似的时候,其实更关注的是中低频部分的差异度。


在实践中,我们可以把图片从 RGB 转换为 YCbCr 格式,只提取 Y 的部分参与计算,实现降维,以减少运算量。再把图片缩放到 32*32 大小,丢弃掉大部分高频信息。由于进行了降维和缩放,后续步骤我们的运算量已大大减少。


把图片从空域转换到频域,我们需要使用 DCT(二维离散余弦变换)。DCT 也是 JPEG 以及 H264 压缩算法的核心部分,感兴趣的可以继续深入了解视频压缩算法的相关研究。

感知哈希与 DCT(离散余弦变换)

为了让大家深入了解背后的原理,这里打算展开介绍一下 DCT,以及它为什么能检测出来图片的相似程度。本文恐怕是网络上能找到讲解 DCT 最详细的一篇文章了,如果你对背后的原理不感兴趣,也可以直接跳过。



从空域到频域


DCT 由如下的公式定义,N 和 M 为矩阵的行数和列数


\begin{equation}F(u, v) = \left (\frac{2}{N} \right )^{\frac{1}{2}} \left (\frac{2}{M} \right )^{\frac{1}{2}} C(u)C(v) \sum_{i=0}^{N-1}\sum_{j=0}^{M-1} f(i,j)cos\left [\frac{\left(2i+1\right)u\pi}{2N} \right ]cos\left [\frac{\left(2j+1\right)v\pi}{2N} \right ]\end{equation}



其中:


  • u,v = 离散频率变量(0,1,2…7)

  • f(i,j) = 图像在 i 行 j 列的像素值

  • F(u,v) = DCT 结果


我们先研究一个最简单的场景,假设图片像素值如下:



当 N 和 M 都为 2 时,上述公式可简化为:


\begin{equation}F(u,v) = C(u)C(v) \sum_{i=0}^{1}\sum_{j=0}^{1} f(i,j)cos\left [\frac{\left(2i+1\right)u\pi}{4} \right] cos\left [\frac{\left(2j+1\right)v\pi}{4} \right]\end{equation}


下面我们来计算二维 DCT



即,结果是:



用 Python 的相关模块可以交叉验证我们的计算结果:


>>> import numpy as np>>> from scipy.fftpack import dct>>> d=np.matrix([[1,3],[2,0]])>>> dct(dct(d,axis=0,norm="ortho"),axis=1,norm="ortho")array([[ 3.,  0.],       [ 1., -2.]])
复制代码


在实践上,上述方式的计算效率不高,更加简便的计算方式是使用 DCT 矩阵:



若 N 取 2,得到 DCT 矩阵



若 N 取 8,得到的矩阵是这样的



其中 i=0 时,即第 0 行,称为 DC 分量,i=1-7 成为 AC 分量,用图表形式表示如下



i=1



i=2



i=3



i=4



i=5



i=6



i=7


有这样一个矩阵的话,我们再进行 DCT 变换就非常简单了:



其中:


  • T = DCT 矩阵

  • M = 图像数据

  • D = DCT 结果


这是对一张 8*8 图片应用 DCT 变换得到的矩阵结果:



这个矩阵最左上角是低频信息,右下角是高频信息。有个神奇的东西叫基准样式。



信不信由你,任意一张 8*8 的图,都可以由标准图中的的小图以一定比例叠加而合成,而每个小图的权重,由 DCT 变换得到的矩阵决定,是不是很有意思。DCT 变换后左上角一般是比较大的数字,而右下角一般是比较小的数字,这暗含了图片中低频信息占的比重较多,因此我们在做图片或者视频编码压缩的时候,正是通过量化舍弃右下角的高频信息,来实现信息的压缩。

图片差异度

我们在对比图片差异的时候,正是通过对比频域信息来实现的。在我们的实现中,首先把软硬件解码后的图片转成 YCbCr 格式,只提取其中的 Y,实现降维,再把图片缩放到 32*32 大小,进一步减少运算量,同时舍弃了一部分高频信息。再应用 32*32 的 DCT 把图片转换到频域,从频域矩阵中提取 8*8 中低频区域的系数,计算算数平均值。



矩阵中的每个值再与 D 比较,大于 D 计 1,小于 D 计 0,按位存储,我们即可得到一个图片指纹。通过计算两个图片指纹的差异,我们就可以得到可以量化图片差异度的数字。


当差异为 0 时,我们认为两张图片完全一样,差异越大,表明图片越不相似。对于解码出现绿屏,花屏的情况,我们可以有效的检测出来。


绿屏案例,相似度 24:



花屏案例,相似度 20:



检测 Demo 截图:



2018-11-21 17:003440

评论 1 条评论

发布
暂无评论
发现更多内容

博文视点算法书单|让算法学习不再难

博文视点Broadview

勿让 Docker Volume 引发 Terminating Pod

黄久远

Docker 云计算 Kubernetes 容器 云原生

单例模式原来是这么简单?!

后台技术汇

28天写作 2月春节不断更

面试杀手锏!2021最新Android常用开源库总结,Android校招面试指南

欢喜学安卓

android 程序员 面试 移动开发

new的过程是怎样的?看完这一篇就懂了

codevald

Java JVM原理 面向对象编程 类对象

List去除重复数据的五种方式

xcbeyond

Java ArrayList 28天写作

运动健身市场越来越大,你的客户却越来越少?

IoT云工坊

人工智能 App 物联网 健身房 智能健身房

LeetCode题解:69. x 的平方根,二分查找,JavaScript,详细注释

Lee Chen

算法 大前端 LeetCode

CodeDay#5 全程回顾——一场关于动态化开发实践的技术探讨

蚂蚁集团移动开发平台 mPaaS

mPaaS Codeday 技术沙龙

MySQL字段类型最全解析

Simon

MySQL 数据库数据类型

软件架构模式之事件驱动架构

架构精进之路

软件架构 七日更 28天写作 2月春节不断更

最基础的3道java面试题,你真的答得上来吗

田维常

面试

字节面试太刁钻了:不加机器,怎么提升系统并发100倍

Java架构师迁哥

疫情又反扑,除了不乱跑,我们还能干点啥?

数据君

【内含福利】流行在CDN圈内的黑话有哪些?

阿里云Edge Plus

CDN

云话题 | 第3期 你女朋友在买买买时,程序员小哥在干嘛?

阿里云Edge Plus

CDN 直播 直播带货

GitHub星标数超4.2万的火爆之作!

博文视点Broadview

k8s-client-go源码剖析(三)

远鹏

Kubernetes Kubernetes源码 Go 语言

面试看这个就够了!6年菜鸟开发面试字节跳动安卓研发岗,学习路线+知识点梳理

欢喜学安卓

android 程序员 面试 移动开发

点赞系统软件开发

luluhulian

GraphX 在图数据库 Nebula Graph 的图计算实践

NebulaGraph

图数据库 图数据库实战

2020已过,2021来临,iOS 开发市场如何?一切都是未知!【未来可期】

ios 程序员

领域的边界,一个小讨论

李小腾

领域驱动设计 DDD

滴滴 Flink-1.10 升级之路

Apache Flink

flink

话题讨论 | 你现在还会推荐亲朋做程序员吗?

石云升

话题讨论 2月春节不断更

第三周

ALone

疫情成本遭不住?一招降本85%,架构特性全部公开!

数据君

谁再把IDEA的Project比作Eclipse的Workspace,我就跟谁急

YourBatman

eclipse IntelliJ IDEA Project Workspace

DIY一款能随周围环境变化的智能灯泡,求婚必备!

IoT云工坊

人工智能 物联网 人脸识别 sdk IoT App

Elasticsearch 从 0 到千万级数据查询实践

📿

Java spring elasticsearch Spring Cloud spring data

这只猫在云端定居了?边缘计算在天猫精灵云应用上的落地实践

阿里云Edge Plus

CDN IoT 边缘计算 云桌面

图片相似度计算:深入理解DCT变换以及感知哈希_移动_柳永峰_InfoQ精选文章