В поле поиска уже появились функции, связанные с «поиском похожих картинок/похожих товаров», такие как карта поиска Google, карта поиска Baidu, продукты поиска фотографий Taobao и т. д. Чтобы добиться аналогичной функции вычисления схожести изображений, в дополнение к использованию «искусственного интеллекта», который звучит высокопарно, на самом деле, с помощью js и нескольких простых алгоритмов можно добиться подобных эффектов вплотную.
Прежде чем читать эту статью,настоятельно рекомендуетсяСначала прочитайте многолетнее письмо Жуань Ифэна.«Принцип поиска похожих изображений»Связанные статьи, алгоритмы, используемые в этой статье, также основаны на них.
Для простоты понимания каждый алгоритм будет проходить два этапа: «извлечение признаков» и «сравнение признаков». Далее мы сосредоточимся на подробной интерпретации шагов «извлечения признаков» каждого алгоритма, а «сравнение признаков» будет объяснено отдельно.
Средний алгоритм хеширования
Обратитесь к большой статье, средний алгоритм хеш-алгона в основном состоит из следующих этапов:
Первый шаг — уменьшить размер до 8×8, чтобы удалить детали изображения, сохранить только основную информацию, такую как структура, свет и тень, и отбросить различия изображения, вызванные разными размерами и пропорциями.
Второй шаг — упростить цвет. Преобразуйте уменьшенное изображение в изображение в градациях серого.
Третий шаг – вычисление среднего значения. Вычисляет среднее значение оттенков серого для всех пикселей.
Четвертый шаг — сравнить оттенки серого пикселей. Сравните оттенки серого 64 пикселей со средним значением. Если оно больше или равно среднему значению, оно записывается как 1, если оно меньше среднего значения, оно записывается как 0.
Пятый шаг — вычисление значения хеш-функции. Результаты сравнения предыдущего шага объединяются для формирования 64-битного целого числа, которое является отпечатком этого изображения.
Шестой шаг заключается в вычислении разницы значений хеш-функции для получения подобия (расстояние Хэмминга или значение косинуса).
После понимания принципа и шагов «алгоритма среднего хеширования» можно приступать к кодированию. Чтобы сделать код более читабельным, я буду использовать машинописный текст для всех примеров в этой статье.
Сжатие изображения:
Мы используем холстdrawImage()метод для достижения сжатия изображения, а затем используйтеgetImageData()способ получитьImageDataобъект.
export function compressImg (imgSrc: string, imgWidth: number = 8): Promise<ImageData> {
return new Promise((resolve, reject) => {
if (!imgSrc) {
reject('imgSrc can not be empty!')
}
const canvas = document.createElement('canvas')
const ctx = canvas.getContext('2d')
const img = new Image()
img.crossOrigin = 'Anonymous'
img.onload = function () {
canvas.width = imgWidth
canvas.height = imgWidth
ctx?.drawImage(img, 0, 0, imgWidth, imgWidth)
const data = ctx?.getImageData(0, 0, imgWidth, imgWidth) as ImageData
resolve(data)
}
img.src = imgSrc
})
}
Некоторые читатели могут спросить, зачем использовать холст для сжатия изображения? Проще говоря, чтобы нарисовать «большую картинку» на «маленьком холсте», часто удаляются некоторые соседние пиксели с похожими цветами, что эффективно уменьшает количество информации в картинке, поэтому можно добиться эффекта сжатия:
надcompressImg()функция, мы используемnew Image()Загрузите изображение, затем установите предустановленное значение ширины и высоты изображения, чтобы сжать изображение до указанного размера, и, наконец, получите сжатое изображение.ImageDataДанные. Это также означает, что мы можем получить информацию о каждом пикселе изображения.
Чтобы преобразовать цветное изображение в изображение в градациях серого, мы должны сначала понять концепцию «изображения в градациях серого». Вот как изображения в градациях серого описываются в Википедии:
В компьютерном мире цифровое изображение в градациях серого — это изображение только с одним выбранным цветом на пиксель.
В большинстве случаев любой цвет может быть составлен из яркости трех цветовых каналов (R, G, B) и цветового пространства (A), а пиксель отображает только один цвет, поэтому можно получить соответствие «пиксель => RGBA». . И «каждый пиксель имеет только один дискретизированный цвет», что означает, что три основных цветовых канала, составляющих этот пиксель, равны по яркости, поэтому нужно вычислить только среднее значение RGB:
// 根据 RGBA 数组生成 ImageData
export function createImgData (dataDetail: number[]) {
const canvas = document.createElement('canvas')
const ctx = canvas.getContext('2d')
const imgWidth = Math.sqrt(dataDetail.length / 4)
const newImageData = ctx?.createImageData(imgWidth, imgWidth) as ImageData
for (let i = 0; i < dataDetail.length; i += 4) {
let R = dataDetail[i]
let G = dataDetail[i + 1]
let B = dataDetail[i + 2]
let Alpha = dataDetail[i + 3]
newImageData.data[i] = R
newImageData.data[i + 1] = G
newImageData.data[i + 2] = B
newImageData.data[i + 3] = Alpha
}
return newImageData
}
export function createGrayscale (imgData: ImageData) {
const newData: number[] = Array(imgData.data.length)
newData.fill(0)
imgData.data.forEach((_data, index) => {
if ((index + 1) % 4 === 0) {
const R = imgData.data[index - 3]
const G = imgData.data[index - 2]
const B = imgData.data[index - 1]
const gray = ~~((R + G + B) / 3)
newData[index - 3] = gray
newData[index - 2] = gray
newData[index - 1] = gray
newData[index] = 255 // Alpha 值固定为255
}
})
return createImgData(newData)
}
ImageData.dataЯвляетсяUint8ClampedArrayМассив, который можно понимать как «массив RGBA», каждое число в массиве принимает значение от 0 до 255, а каждая группа из 4 чисел представляет значение RGBA пикселя. из-заImageDataДля объекта только для чтения, поэтому вы должны написать еще один.creaetImageData()метод, используяcontext.createImageData()создать новыйImageDataобъект.
После получения изображения в градациях серого можно выполнить операцию извлечения отпечатка пальца.
Извлечение отпечатков пальцев
В «Алгоритме среднего хеширования», если значение серого пикселя изображения в градациях серого больше среднего значения, оно считается равным 1, в противном случае оно равно 0. Комбинация этой части информации является отпечатком изображения. Поскольку у нас уже есть изображение в градациях серогоImageDataобъект, становится легко извлечь отпечатки пальцев:
Выполнив описанную выше серию шагов, мы можем получить информацию об отпечатках пальцев изображения с помощью «алгоритма среднего хеширования» (примером является изображение в градациях серого размером 8 × 8):
Проще говоря, после того, как алгоритм подвергнется дискретному косинусному преобразованию, изображение преобразуется из пиксельной области в частотную область, а низкочастотные составляющие, несущие эффективную информацию, будут сосредоточены в верхнем левом углу матрицы DCT, поэтому мы можем используйте эту функцию, чтобы извлечь особенности изображения.
Шаги алгоритма следующие:
Уменьшение размера: pHash начинается с маленькой картинки, но картинка больше 88, 3232 лучше всего. Целью этого является упрощение расчета DCT, а не снижение частоты.
Упростить цвет: преобразовать изображение в изображение в градациях серого для дальнейшего упрощения вычислений.
Вычислить DCT: Вычислите DCT-преобразование изображения, чтобы получить матрицу коэффициентов DCT 32*32.
Уменьшенный DCT: хотя результат DCT равен 32Матрица 32 размера, но нам нужно сохранить только 8 верхних левых угловМатрица 8, эта часть представляет самые низкие частоты на картинке.
Вычислите среднее значение: вычислите среднее значение DCT так же, как среднее значение хэша.
Рассчитайте хэш-значение: это самый важный шаг.В соответствии с матрицей DCT 8 * 8 установите 64-битное хэш-значение 0 или 1. Значение, большее или равное среднему значению DCT, устанавливается на «1». , а значение меньше среднего значения DCT устанавливается равным "0" . Объединенные вместе, они образуют 64-битное целое число, которое является отпечатком этого изображения.
Вернувшись в код, сначала добавьте метод DCT:
function memoizeCosines (N: number, cosMap: any) {
cosMap = cosMap || {}
cosMap[N] = new Array(N * N)
let PI_N = Math.PI / N
for (let k = 0; k < N; k++) {
for (let n = 0; n < N; n++) {
cosMap[N][n + (k * N)] = Math.cos(PI_N * (n + 0.5) * k)
}
}
return cosMap
}
function dct (signal: number[], scale: number = 2) {
let L = signal.length
let cosMap: any = null
if (!cosMap || !cosMap[L]) {
cosMap = memoizeCosines(L, cosMap)
}
let coefficients = signal.map(function () { return 0 })
return coefficients.map(function (_, ix) {
return scale * signal.reduce(function (prev, cur, index) {
return prev + (cur * cosMap[L][index + (ix * L)])
}, 0)
})
}
Затем добавьте два метода матричной обработки, а именно масштабирование одномерного массива, сгенерированного методом DCT, в двумерный массив (матрицу) и получение из матрицы его содержимого «левого верхнего угла».
// 一维数组升维
function createMatrix (arr: number[]) {
const length = arr.length
const matrixWidth = Math.sqrt(length)
const matrix = []
for (let i = 0; i < matrixWidth; i++) {
const _temp = arr.slice(i * matrixWidth, i * matrixWidth + matrixWidth)
matrix.push(_temp)
}
return matrix
}
// 从矩阵中获取其“左上角”大小为 range × range 的内容
function getMatrixRange (matrix: number[][], range: number = 1) {
const rangeMatrix = []
for (let i = 0; i < range; i++) {
for (let j = 0; j < range; j++) {
rangeMatrix.push(matrix[i][j])
}
}
return rangeMatrix
}
Повторно используйте функцию преобразования оттенков серого, ранее написанную в «Алгоритме среднего хеширования».createGrayscale(), мы можем получить собственные значения «алгоритма перцептивного хеширования»:
Во-первых, отрывок из описания Руан Да «метода распределения цвета»:
Руан Да упростил 256 цветовых значений до 4. Исходя из этого принципа, при построении алгоритма метода цветового распределения можно задать деление этого интервала модифицируемым, единственное требование — количество интервалов должно делиться на 256. Алгоритм следующий:
// 划分颜色区间，默认区间数目为4个
// 把256种颜色取值简化为4种
export function simplifyColorData (imgData: ImageData, zoneAmount: number = 4) {
const colorZoneDataList: number[] = []
const zoneStep = 256 / zoneAmount
const zoneBorder = [0] // 区间边界
for (let i = 1; i <= zoneAmount; i++) {
zoneBorder.push(zoneStep * i - 1)
}
imgData.data.forEach((data, index) => {
if ((index + 1) % 4 !== 0) {
for (let i = 0; i < zoneBorder.length; i++) {
if (data > zoneBorder[i] && data <= zoneBorder[i + 1]) {
data = i
}
}
}
colorZoneDataList.push(data)
})
return colorZoneDataList
}
Упростив значения цвета, вы можете классифицировать их по разным группам:
Наконец, вам нужно только подсчитать общее количество каждой идентичной группы:
export function getFingerprint (zonedList: string[], zoneAmount: number = 16) {
const colorSeperateMap: {
[key: string]: number
} = {}
for (let i = 0; i < zoneAmount; i++) {
for (let j = 0; j < zoneAmount; j++) {
for (let k = 0; k < zoneAmount; k++) {
colorSeperateMap[JSON.stringify([i, j, k])] = 0
}
}
}
zonedList.forEach(zone => {
colorSeperateMap[zone]++
})
return Object.values(colorSeperateMap)
}
метод характеристик контента
«Метод признаков контента» относится к методу преобразования изображения в изображение в градациях серого и последующего преобразования его в «бинарное изображение», а затем формирования отпечатка пальца в соответствии со значением пикселя (черного или белого) для сравнения. Суть этого алгоритма заключается в том, чтобы найти «порог» для создания бинарного изображения.
Для создания оттенков серого RGB отличается от подхода, используемого в среднем, упомянутого в «алгоритме среднего хеширования», где мы используем взвешенный метод для достижения. Зачем ты это делаешь? Здесь дело доходит до раскраски некоторых усвоенных понятий.
Изображение в градациях серого со средним RGB — самый простой подход, но он игнорирует длины волн красного, зеленого и синего и их влияние на изображение в целом. Если взять следующий рисунок в качестве примера, если среднее значение RGB получено непосредственно как оттенки серого, обработанное изображение в градациях серого будет темным в целом, что вызовет большие помехи для последующего создания бинарных изображений.
Так как же можно улучшить эту ситуацию? Ответ заключается в добавлении разных весов к трем цветам RGB. Учитывая, что красный свет имеет большую длину волны, а зеленый свет имеет более короткую длину волны и относительно менее зрительно стимулирует, мы должны намеренно уменьшить вес красного света и увеличить вес зеленого света. После статистики лучшим соотношением распределения весов будет R:G:B = 0,299:0,587:0,114.
Итак, мы можем получить обработчики оттенков серого:
enum GrayscaleWeight {
R = .299,
G = .587,
B = .114
}
function toGray (imgData: ImageData) {
const grayData = []
const data = imgData.data
for (let i = 0; i < data.length; i += 4) {
const gray = ~~(data[i] * GrayscaleWeight.R + data[i + 1] * GrayscaleWeight.G + data[i + 2] * GrayscaleWeight.B)
data[i] = data[i + 1] = data[i + 2] = gray
grayData.push(gray)
}
return grayData
}
Приведенная выше функция возвращаетgrayDataмассив внутриКаждый элемент представляет значение серого пикселя(Поскольку RBG принимает одно и то же значение, требуется только одно значение). Далее используется «метод Оцу» для вычисления порога бинарного изображения. Что касается «Закона Дацзин», статья Жуан Да уже подробно объяснила его, поэтому я не буду его здесь распространять. я здесьэто местоНашел Java-реализацию "метода Оцу", а позже изменил ее на js-версию с небольшой модификацией:
/ 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
}
OTSUAlgorithm()функция получаетImageDataобъект, после предыдущего шагаtoGray()После того, как метод получает список значений серого, он вычисляет оптимальное пороговое значение в соответствии с «методом Оцу», а затем возвращается. Затем используйте этот порог, чтобы обработать исходное изображение, чтобы получить бинарное изображение.
export function binaryzation (imgData: ImageData, threshold: number) {
const canvas = document.createElement('canvas')
const ctx = canvas.getContext('2d')
const imgWidth = Math.sqrt(imgData.data.length / 4)
const newImageData = ctx?.createImageData(imgWidth, imgWidth) as ImageData
for (let i = 0; i < imgData.data.length; i += 4) {
let R = imgData.data[i]
let G = imgData.data[i + 1]
let B = imgData.data[i + 2]
let Alpha = imgData.data[i + 3]
let sum = (R + G + B) / 3
newImageData.data[i] = sum > threshold ? 255 : 0
newImageData.data[i + 1] = sum > threshold ? 255 : 0
newImageData.data[i + 2] = sum > threshold ? 255 : 0
newImageData.data[i + 3] = Alpha
}
return newImageData
}
Если размер изображения N×N, в соответствии с характеристикой «черное или белое» бинарного изображения мы можем получить матрицу N×N 0-1, которая является отпечатком пальца:
Алгоритм выравнивания функций
Получив разные типы отпечатков (признаков) изображений разными способами, как мы должны их сравнивать? Здесь будут представлены три алгоритма выравнивания, а затем будут проанализированы ситуации, в которых эти алгоритмы применимы.
Расстояние Хэмминга
Абстрактный раздел Википедии с описанием «расстояния Хэмминга»:
В теории информации расстояние Хэмминга между двумя строками одинаковой длины — это количество различных символов в соответствующих позициях двух строк. Другими словами, это то, что нужно для преобразования одной строки в другую.заменятьколичество символов.
Например:
Расстояние Хэмминга между 1011101 и 1001001 равно 2.
Расстояние Хэмминга между 2143896 и 2233796 равно 3.
Расстояние Хэмминга между «тонированными» и «розами» равно 3.
Поняв смысл, мы можем написать метод для вычисления расстояния Хэмминга:
использовать этотhammingDistance()метод, чтобы проверить пример в Википедии:
Результаты проверки соответствуют ожиданиям.
Зная расстояние Хэмминга, вы также можете узнать сходство между двумя строками одинаковой длины (чем меньше расстояние Хэмминга, тем больше сходство):
相似度 = (字符串长度 - 汉明距离) / 字符串长度
косинусное сходство
Из Википедии мы можем узнать об определении косинусного подобия:
Косинусное сходство измеряет сходство между двумя векторами путем измерения косинуса их угла. Косинус угла 0 градусов равен 1, а косинус любого другого угла не больше 1, а его минимальное значение равно -1. Таким образом, косинус угла между двумя векторами определяет, указывают ли два вектора примерно в одном направлении. Когда два вектора имеют одинаковое направление, значение косинусного сходства равно 1; когда угол между двумя векторами равен 90°, значение косинусного сходства равно 0; когда два вектора указывают в совершенно противоположных направлениях, значение косинусного сходства равно значение равно -1. Этот результат не зависит от длины вектора, он связан только с направлением вектора. Косинусное сходство обычно используется в положительных пространствах, поэтому ему присваивается значение от 0 до 1.
Обратите внимание, что эти верхние и нижние границы верны для векторных пространств любой размерности, а косинусное подобие чаще всего используется для многомерных положительных пространств.
Косинусное подобие может вычислять угол между двумя векторами, что интуитивно указывает, подобны ли два вектора по направлению, что очень полезно для вычисления подобия двух матриц N×N 0-1. По формуле косинусного подобия можно написать ее js реализацию:
export function cosineSimilarity (sampleFingerprint: number[], targetFingerprint: number[]) {
// cosθ = ∑n, i=1(Ai × Bi) / (√∑n, i=1(Ai)^2) × (√∑n, i=1(Bi)^2) = A · B / |A| × |B|
const length = sampleFingerprint.length
let innerProduct = 0
for (let i = 0; i < length; i++) {
innerProduct += sampleFingerprint[i] * targetFingerprint[i]
}
let vecA = 0
let vecB = 0
for (let i = 0; i < length; i++) {
vecA += sampleFingerprint[i] ** 2
vecB += targetFingerprint[i] ** 2
}
const outerProduct = Math.sqrt(vecA) * Math.sqrt(vecB)
return innerProduct / outerProduct
}
Применимые сценарии двух алгоритмов выравнивания
После понимания двух алгоритмов сравнения признаков «расстояние Хэмминга» и «косинусное сходство» мы должны увидеть, к каким алгоритмам извлечения признаков они применимы.
Давайте сначала посмотрим на «метод распределения цвета». В «методе распределения цветов» цвет изображения мы делим на интервалы, а признаки получаем путем подсчета количества различных цветовых интервалов, тогда собственные значения здесь связаны с «количеством», то есть не- матрица 0-1.
Очевидно, что для сравнения сходства двух признаков «метода цветового распределения» «расстояние Хэмминга» неприменимо и может быть рассчитано только по «косинусному сходству».
Затем посмотрите на «Алгоритм среднего хеширования» и «Метод характеристик контента». По результатам оба алгоритма выделения признаков могут получить матрицу N×N 0-1, причем значение элементов в матрице не имеет ничего общего с «числом», только 0-1 балл. Таким образом, они подходят для вычисления подобия по «расстоянию Хэмминга» и «косинусному сходству» одновременно.
точность расчета
После понимания того, как извлекать признаки изображений и как их сравнивать, самое главное — понять точность их вычисления для подобия.
Сходство, упомянутое в этой статье, достигается только с помощью объективных алгоритмов, и оценка того, являются ли две картинки «похожими», является очень субъективным вопросом. Поэтому я написал простой сервис, который вычисляет сходство между двумя изображениями по разным алгоритмам и с разной точностью:
После многократного сравнения различных материалов я пришел к следующемуочень субъективнозаключение.
Для двух изображений с более насыщенными цветами и большим количеством деталей результат расчета «метода цветового распределения» является наиболее интуитивным.
Для двух изображений с похожим содержимым, но с большой разницей в цвете, как «метод признаков содержимого», так и «алгоритм среднего/перцептивного хэширования» могут дать интуитивно понятные результаты.
Для «метода цветового распределения» количество интервалов оказывает большое влияние на результаты расчета, и очень важно выбрать подходящий интервал.
Подводя итог, можно сказать, что три алгоритма выделения признаков и два алгоритма сравнения признаков имеют свои преимущества и недостатки, и их следует гибко выбирать для различных ситуаций в практических приложениях.
Суммировать
Эта статья читает две статьи Руан Ифэн.«Принцип поиска похожих изображений»Впоследствии это делается после подведения итогов собственной практики. Так как понимание цвета, математики и других областей находится лишь на поверхностном уровне, статья неизбежно будет содержать неточности.Если вы найдете что-то неправильно выраженное, пожалуйста, оставьте сообщение и укажите на это, и я вовремя исправлю.
