/ OTSU algorithm
// rewrite from http://www.labbookpages.co.uk/software/imgProc/otsuThreshold.html
export function OTSUAlgorithm (imgData: ImageData) {
const grayData = toGray(imgData)
let ptr = 0
let histData = Array(256).fill(0)
let total = grayData.length
while (ptr < total) {
let h = 0xFF & grayData[ptr++]
histData[h]++
}
let sum = 0
for (let i = 0; i < 256; i++) {
sum += i * histData[i]
}
let wB = 0
let wF = 0
let sumB = 0
let varMax = 0
let threshold = 0
for (let t = 0; t < 256; t++) {
wB += histData[t]
if (wB === 0) continue
wF = total - wB
if (wF === 0) break
sumB += t * histData[t]
let mB = sumB / wB
let mF = (sum - sumB) / wF
let varBetween = wB * wF * (mB - mF) ** 2
if (varBetween > varMax) {
varMax = varBetween
threshold = t
}
}
return threshold
}
在搜索领域,早已出现了“查找相似图片/相似商品”的相关功能,如 Google 搜图,百度搜图,淘宝的拍照搜商品等。要实现类似的计算图片相似度的功能,除了使用听起来高大上的“人工智能”以外,其实通过 js 和几种简单的算法,也能八九不离十地实现类似的效果。
特征提取算法
为了便于理解,每种算法都会经过“特征提取”和“特征比对”两个步骤进行。接下来将着重对每种算法的“特征提取”步骤进行详细解读,而“特征比对”则单独进行阐述。
平均哈希算法
参考阮大的文章,“平均哈希算法”主要由以下几步组成:
明白了“平均哈希算法”的原理及步骤以后,就可以开始编码工作了。为了让代码可读性更高,本文的所有例子我都将使用 typescript 来实现。
图片压缩:
我们采用 canvas 的
drawImage()
方法实现图片压缩,后使用getImageData()
方法获取ImageData
对象。可能有读者会问,为什么使用 canvas 可以实现图片压缩呢?简单来说,为了把“大图片”绘制到“小画布”上,一些相邻且颜色相近的像素往往会被删减掉,从而有效减少了图片的信息量,因此能够实现压缩的效果:
在上面的
compressImg()
函数中,我们利用new Image()
加载图片,然后设定一个预设的图片宽高值让图片压缩到指定的大小,最后获取到压缩后的图片的ImageData
数据——这也意味着我们能获取到图片的每一个像素的信息。图片灰度化
为了把彩色的图片转化成灰度图,我们首先要明白“灰度图”的概念。在维基百科里是这么描述灰度图像的:
大部分情况下,任何的颜色都可以通过三种颜色通道(R, G, B)的亮度以及一个色彩空间(A)来组成,而一个像素只显示一种颜色,因此可以得到“像素 => RGBA”的对应关系。而“每个像素只有一个采样颜色”,则意味着组成这个像素的三原色通道亮度相等,因此只需要算出 RGB 的平均值即可:
ImageData.data
是一个 Uint8ClampedArray 数组,可以理解为“RGBA数组”,数组中的每个数字取值为0~255,每4个数字为一组,表示一个像素的 RGBA 值。由于ImageData
为只读对象,所以要另外写一个creaetImageData()
方法,利用context.createImageData()
来创建新的ImageData
对象。拿到灰度图像以后,就可以进行指纹提取的操作了。
指纹提取
在“平均哈希算法”中,若灰度图的某个像素的灰度值大于平均值,则视为1,否则为0。把这部分信息组合起来就是图片的指纹。由于我们已经拿到了灰度图的
ImageData
对象,要提取指纹也就变得很容易了:通过上述一连串的步骤,我们便可以通过“平均哈希算法”获取到一张图片的指纹信息(示例是大小为8×8的灰度图):
感知哈希算法
关于“感知哈希算法”的详细介绍,可以参考这篇文章:《基于感知哈希算法的视觉目标跟踪》。
简单来说,该算法经过离散余弦变换以后,把图像从像素域转化到了频率域,而携带了有效信息的低频成分会集中在 DCT 矩阵的左上角,因此我们可以利用这个特性提取图片的特征。
该算法的步骤如下:
回到代码中,首先添加一个 DCT 方法:
然后添加两个矩阵处理方法,分别是把经过 DCT 方法生成的一维数组升维成二维数组(矩阵),以及从矩阵中获取其“左上角”内容。
复用之前在“平均哈希算法”中所写的灰度图转化函数
createGrayscale()
,我们可以获取“感知哈希算法”的特征值:颜色分布法
首先摘抄一段阮大关于“颜色分布法“的描述:
阮大把256种颜色取值简化成了4种。基于这个原理,我们在进行颜色分布法的算法设计时,可以把这个区间的划分设置为可修改的,唯一的要求就是区间的数量必须能够被256整除。算法如下:
把颜色取值进行简化以后,就可以把它们归类到不同的分组里面去:
最后只需要统计每个相同的分组的总数即可:
内容特征法
”内容特征法“是指把图片转化为灰度图后再转化为”二值图“,然后根据像素的取值(黑或白)形成指纹后进行比对的方法。这种算法的核心是找到一个“阈值”去生成二值图。
对于生成灰度图,有别于在“平均哈希算法”中提到的取 RGB 均值的办法,在这里我们使用加权的方式去实现。为什么要这么做呢?这里涉及到颜色学的一些概念。
具体可以参考这篇《Grayscale to RGB Conversion》,下面简单梳理一下。
采用 RGB 均值的灰度图是最简单的一种办法,但是它忽略了红、绿、蓝三种颜色的波长以及对整体图像的影响。以下面图为示例,如果直接取得 RGB 的均值作为灰度,那么处理后的灰度图整体来说会偏暗,对后续生成二值图会产生较大的干扰。
那么怎么改善这种情况呢?答案就是为 RGB 三种颜色添加不同的权重。鉴于红光有着更长的波长,而绿光波长更短且对视觉的刺激相对更小,所以我们要有意地减小红光的权重而提升绿光的权重。经过统计,比较好的权重配比是 R:G:B = 0.299:0.587:0.114。
于是我们可以得到灰度处理函数:
上述函数返回一个
grayData
数组,里面每个元素代表一个像素的灰度值(因为 RBG 取值相同,所以只需要一个值即可)。接下来则使用“大津法”(Otsu's method)去计算二值图的阈值。关于“大津法”,阮大的文章已经说得很详细,在这里就不展开了。我在这个地方找到了“大津法”的 Java 实现,后来稍作修改,把它改为了 js 版本:OTSUAlgorithm()
函数接收一个ImageData
对象,经过上一步的toGray()
方法获取到灰度值列表以后,根据“大津法”算出最佳阈值然后返回。接下来使用这个阈值对原图进行处理,即可获取二值图。若图片大小为 N×N,根据二值图“非黑即白”的特性,我们便可以得到一个 N×N 的 0-1 矩阵,也就是指纹:
特征比对算法
经过不同的方式取得不同类型的图片指纹(特征)以后,应该怎么去比对呢?这里将介绍三种比对算法,然后分析这几种算法都适用于哪些情况。
汉明距离
摘一段维基百科关于“汉明距离”的描述:
明白了含义以后,我们可以写出计算汉明距离的方法:
使用这个
hammingDistance()
方法,来验证下维基百科上的例子:验证结果符合预期。
知道了汉明距离,也就可以知道两个等长字符串之间的相似度了(汉明距离越小,相似度越大):
余弦相似度
从维基百科中我们可以了解到关于余弦相似度的定义:
余弦相似度可以计算出两个向量之间的夹角,从而很直观地表示两个向量在方向上是否相似,这对于计算两个 N×N 的 0-1 矩阵的相似度来说非常有用。根据余弦相似度的公式,我们可以把它的 js 实现写出来:
两种比对算法的适用场景
明白了“汉明距离”和“余弦相似度”这两种特征比对算法以后,我们就要去看看它们分别适用于哪些特征提取算法的场景。
首先来看“颜色分布法”。在“颜色分布法”里面,我们把一张图的颜色进行区间划分,通过统计不同颜色区间的数量来获取特征,那么这里的特征值就和“数量”有关,也就是非 0-1 矩阵。
显然,要比较两个“颜色分布法”特征的相似度,“汉明距离”是不适用的,只能通过“余弦相似度”来进行计算。
接下来看“平均哈希算法”和“内容特征法”。从结果来说,这两种特征提取算法都能获得一个 N×N 的 0-1 矩阵,且矩阵内元素的值和“数量”无关,只有 0-1 之分。所以它们同时适用于通过“汉明距离”和“余弦相似度”来计算相似度。
计算精度
明白了如何提取图片的特征以及如何进行比对以后,最重要的就是要了解它们对于相似度的计算精度。
本文所讲的相似度仅仅是通过客观的算法来实现,而判断两张图片“像不像”却是一个很主观的问题。于是我写了一个简单的服务,可以自行把两张图按照不同的算法和精度去计算相似度:
https://img-compare.netlify.com/
经过对不同素材的多方比对,我得出了下列几个非常主观的结论。
总结一下,三种特征提取算法和两种特征比对算法各有优劣,在实际应用中应该针对不同的情况灵活选用。
总结
本文是在拜读阮一峰的两篇《相似图片搜索的原理》之后,经过自己的实践总结以后而成。由于对色彩、数学等领域的了解只停留在浅显的层面,文章难免有谬误之处,如果有发现表述得不正确的地方,欢迎留言指出,我会及时予以更正。