Фотогалерея на максималках16.09.2021 14:32

~1 год назад я начал разрабатывать свою фотогалерею (песочницу для теста всяких технологий). Данная статья — это описание её архитектуры, а также различные твики/лайфхаки/микрогайды которые я узнал за время разработки + немного про производительность.

image-loader.svg

Монолит

Вначале был монолит. Я пытался написать всю логику на javascript — использовал биндинги OpenCV для js, библиотеки для вычисления phash на js, и так далее. После непродолжительной войны с утечками памяти, плохой производительностью и ограниченным функционалом, было решено вынести поиск в отдельный сервис на python. Так проект обрел модульную структуру:

  • scenery — frontend, backend

  • ambience — Все связанное с поиском изображений

  • crud_file_server — отдельный микросервис для бекапа и ipfs.

Архитектура на текущий моментАрхитектура на текущий момент

Nginx в качестве reverse proxy сервера. Там осуществляется шифрование (https), компрессия (gzip/brotli) и раздача статики, чтобы разгрузить Node.js.

nginx

Пара твиков для nginx.

Так как мы используем cloudflare, разумно запретить все запросы которые идут не от cloudflare. Скрипт allow_cloudflare.sh создает allow-cloudflare-only.conf, whitelist состоящий из ip адресов cloudflare. Остается только его заимпортить.

include /etc/nginx/allow-cloudflare-only.conf;

Next.js при сборке приложения добавляет хеш к названиям файлов, поэтому можно сказать, что файл с определенным именем никогда не поменяет свое содержимое. Эту информацию можно использовать для ускорения сайта — для статических файлов выставим большой max-age и атрибут immutable, который говорит браузеру не ревалидировать кеш. Классный атрибут, к сожалению, мало где поддерживается.

файлы

image-loader.svg
expires 1y;
add_header Cache-Control "public, immutable";

scenery

Текущий стек: Node.js + MongoDB + TypeScript + Next.js + Fastify + Material UI

Я использую Next.js, т.к на текущий момент это наиболее популярный и удобный react фреймворк, который поддерживает CSR (Client-side rendering), SSR (server-side rendering) и ISR (Incremental Static Regeneration). По сути, ISR это SSR с кешем, у которого мы можем задать параметр revalidate, время жизни кеша. Этот кеш ревалидируется в фоновом режиме, после запроса пользователя. Его удобно использовать для отображения страниц, которые требуют много вычислительных ресурсов/времени на генерацию (например, страница с различной статистикой)

ISR

image-loader.svg

Полезные твики для next.js

module.exports = {
  poweredByHeader: false,  //отключить заголовок x-powered-by 
  compress: false,    //отключить gzip сжатие (т.к сжимаем на nginx или на cdn)
}

Компрессия статики с помощью Brotli

const zlib = require("zlib")
const CompressionPlugin = require("compression-webpack-plugin")
const use_brotli = false
module.exports = {
  webpack: (config, { isServer }) => {
    if (use_brotli && !isServer) {
      config.plugins.push(
        new CompressionPlugin({
          filename: "[path][base].br",
          algorithm: "brotliCompress",
          test: /\.(js|css|html)$/,
          compressionOptions: {
            params: {
              [zlib.constants.BROTLI_PARAM_QUALITY]: 11,
            },
          }
        })
      )
    }
    return config
  }
}

Самый тяжелый статический файл — framework.js
framework-0441fae7fd130f37dee1.js — 131,009 bytes
framework-0441fae7fd130f37dee1.js.br — 36,934 bytes

Для сравнения (gzip level 9)
framework-0441fae7fd130f37dee1.js.gz — 42,388 bytes

Мощно. Жаль, что Cloudflare не поддерживает brotli на своих Edge серверах. Так что 11 левелом brotli попользоваться не получится, но Cloudflare сам применяет какой-то уровень brotli, так что потери не такие большие. (Сloudflare сжал тот же файл до 43.4 кб).

Изоморфные конфиг файлы могут быть опасны.

Ошибка, которую легко допустить.

В файле config.js экспортируется объект с различными секретами для backend и конфигами, как для серверной, так и для клиентской части.

В клиентской части объект импортируется и используется какое-то из его свойств, например recaptcha_site_key. По дефолту, webpack инлайнит config.js целиком, в результате секреты бекенда отправляются на клиент.

В файле next.config.js можно указать какие данные нужно заинлайнить (реализовано через DefinePlugin)

module.exports = {
  env: {  //https://nextjs.org/docs/api-reference/next.config.js/environment-variables
    recaptcha_site_key: "6LcqV9QUAAAAAEybBVr0FWnUnFQmOVxGoQ_Muhtb",
    api_domain: "http://localhost/public_api",
    reverse_search_url: "http://localhost",
    domain: "http://localhost",
    ipns: "ipns.scenery.cx"
  },
}

Далее в клиентской части просто используем process.env.название_переменной. Значение будет заинлайнено.

Next.js SSR не минифицирует css, который инлайнится в html страницу (если у вас кастомный _document.js).

Напишем миникеш — будем хранить минифицированный css в Map. Если сгенерированный css есть в Map, возвращаем его минифицированную версию, иначе минифицируем и добавляем в Map.

let css = sheets.toString()
  if (css && process.env.NODE_ENV === "production") {
    const min_css = minified_css_cache.get(css)
    if (min_css) {
      css = min_css
    } else {
      const old_css = css
      css = cleanCSS.minify(css).styles
      minified_css_cache.set(old_css, css)
    }
  }

Убирает пару десятых килобайта, практически не влияет на производительность (стало даже немного быстрее). Если у вас много разного динамического css’a, то надо будет потестировать, возможно плюсы от минификации перекроются размером Map/его быстродействием.

Веб фреймворк

В начале разработки я выбрал Express. Простой синтаксис, множество плагинов. Есть только 1 минус — низкая производительность.

image-loader.svg

Решил попробовать переписать все на fastify, благо кода не так много. Получил прирост с 50 req/s до 70 req/s. Это довольно много, учитывая что я отправлял запросы на страницы, которые обрабатываются с помощью Next.js, т.е все что требуется от веб фреймворка, это передать запрос обработчику Next.js, который выполняет самое длительное действие — рендеринг страницы. Получается, что express съедал около 30 процентов производительности.

Особенно мне понравилась связка валидации (встроенная валидация в fastify реализована с помощью ajv) и модуля json-schema-to-ts. Эта связка позволяет использовать типы, которые мы указали при валидации, в typescript. Т.е. если мы указали что body обязан иметь свойство id типа number, то в ts тип req.body.id тоже будет number.

Скриншот из VS Code

image-loader.svg

Ниже приведен типовой код для обработки пути (route). На мой взгляд, это очень удобно, когда валидация и сам код обработки запроса находятся в одном файле.

Пример кода

import db_ops from './../helpers/db_ops'
import image_ops from './../helpers/image_ops'
import { FastifyRequest, FastifyReply } from "fastify"
import { FromSchema } from "json-schema-to-ts";
const body_schema_delete_image = {
    type: 'object',
    properties: {
        id: { type: 'number' },
    },
    required: ['id'],
} as const

async function delete_image(req: FastifyRequest<{ Body: FromSchema }>, res: FastifyReply) {
    const id = req.body.id
    if (req.session?.user_id) {
        const user = await db_ops.activated_user.find_user_by_id(req.session.user_id)
        if (user && user.isAdmin) {
            const result = await image_ops.delete_image(id)
            if (result) {
                res.send({ message: result })
            } else {
                res.send({ message: "fail" })
            }
        }
    } else {
        res.status(404).send()
    }
}

export default {
    schema: {
        body: body_schema_delete_image
    },
    handler: delete_image
}

Единственный минус — отсутствие некоторых плагинов. Хорошо, что написать плагин для fastify достаточно просто. Я не нашел плагин для верификации Recaptcha, поэтому написал свой. Система хуков позволяет перехватить запрос еще на подходе к хендлеру и вернуть ошибку, не исполняя его основной код. Вот гайд по созданию плагинов. Я лично просто посмотрел как работает несколько плагинов из списка всех плагинов и использовал их код в качестве boilerplate.

Сетка изображений

Отдельно хотелось бы рассказать про то, как генерируется image grid. Средствами css довольно сложно (или практически невозможно) создать динамическую, отзывчивую сетку изображений, где изображения будут сохранять соотношения сторон, а строки максимально упакованы. Вот пример css сетки.

Решение — будем генерировать сетку силами js. Используем https://github.com/neptunian/react-photo-gallery.

Данная библиотека использует адаптацию алгоритма Кнута-Пласса для переноса строк. (Этот алгоритм также используется в TeX для переноса строк)

Алгоритм создает граф возможных переносов, где вершина — это изображение на котором произошёл перенос строки, а вес ребра это cost(targetRowHeight, Высота ряда если перенести строку). Оптимальное размещение изображений — это кратчайший путь в таком графе. Т.е мы получаем равномерно упакованные строки наиболее близкие к требуемой высоте.

Более подробно здесь https://medium.com/google-design/google-photos-45b714dfbed1, (2пункт, Justified Gallery)
http://blog.vjeux.com/2014/image/google-plus-layout-find-best-breaks.html

3d5ed9aa76c20bafa93f6502ddbf0674.jpeg

Оптимизация изображений

Lossless сжатие, т.е пиксели изображения не меняются.

Jpeg сжимаем с помощью jpegtran (рекомендую устанавливать из libjpeg-turbo)  

apt-get install libjpeg-turbo-progs

jpegtran из mozjpeg жмет на 1,18% лучше, но делает это в 2,3 раза медленнее. https://gist.github.com/sergejmueller/088dce028b6dd120a16e

Вместо optipng используем Oxipng (переписанный на Rust optipng с поддержкой многопоточности)

Тест jpegtran

оригинальное изображение — 22,785 KB
После jpegtran — 21,420 KB

Тест oxipng/optipng

оригинальное изображение — 8,94 MB

oxipng -o2 — 5.97 MB, 5 секунд
optipng -o2 — 5.92 MB, 34 секунды

Нарезка thumbnail’ов

Для ресайза изображения используем sharp. Sharp под капотом использует libvips, это очень быстрая и потребляющая мало памяти библиотека для работы с изображениями.

async function generate_thumbnail(image_src: Buffer | string) {  //buffer or path to the image
  const metadata = await sharp(image_src).metadata()
  if (metadata && metadata.height && metadata.width) {
    const x: { width?: number, height?: number } = {}
    if (metadata.width >= metadata.height) {
      x.width = Math.min(metadata.width, 750)
    } else { //metadata.width < metadata.height
      x.height = Math.min(metadata.height, 750)
    }
    const data = await sharp(image_src).resize(x).jpeg({ quality: 80, mozjpeg: true }).toBuffer()
    return data
  } else {
    return null
  }
}

Опция mozjpeg нужна для использования дефолтных настроек от mozjpeg.{ trellisQuantisation: true, overshootDeringing: true, optimiseScans: true, quantisationTable: 3 }

Thumbnail«ы выходят по ~50 кб. На моих тестах, одинаковые по визуальному качеству thumbnail’ы в jpeg весят меньше, чем в webp.

Генерация sha256

Генерируем sha256 до оптимизации (lossless сжатия) изображения. Используем https://github.com/ronomon/crypto-async

Проблемы со стандартным модулем crypto:

  1. Crypto блокирует event loop

  2. Crypto не использует больше 1 ядра

crypto-async

  1. Работает в ThreadPool (т.е не блокирует event loop)

  2. Т.к используется ThreadPool, то масштабируется от количества ядер (по умолчанию количество Thread’ов в пуле равно 4, значение можно увеличить вручную)

  3. Zero copy

Дедупликация

Дедупликация зависит от того как импортировалось изображение. Есть 2 типа импорта: одиночный (через веб интерфейс) и массовый (через python скрипт)

Вот как происходит дедупликация при импорте изображения через веб интерфейс:

Сначала ищем sha256 хеш в бд. Если хеша нет, то передаем картинку в ambience. ambience обращается к phash микросервису, если дубликат не найден, то обращается к akaze микросервису. Полученные результаты отправляются обратно в scenery. Подробнее о том, как работают вышеперечисленные микросервисы, расскажу в секции с описанием работы ambience.

Ввиду того, что возможны ложноположительные результаты, можно отменить проверку на дубликат из веб интерфейса.

Поиск по тегам

Посмотрим, как работают логические выражения в MongoDB

db.things.find({
    $and: [
        {
            $or: [{ "first_name": "john" }, { "last_name": "john" }]
        },
        { "phone": "12345678" }
    ]
})

Данный запрос эквивалентен ({"first_name" : "john"} ||  {"last_name" : "john"}) && {"phone": "12345678"}. Похоже на AST, значит нужно написать парсер, который сможет сгенерировать AST из строки с логическими выражениями.

Для написания парсера я использовал один из самых простых алгоритмов — Алгоритм сортировочной станции (Shunting yard algorithm).

Я довольно долго мучался с этим парсером, из-за чего код стал нечитаемым. Основная проблема была в том, что скобки, знак восклицания и минус могут быть как частью тега, так и оператором. Если хотите потренироваться в понимании обфусцированного кода — добро пожаловать.

Поддерживает:

  • && ,(запятая) — логическое и

  • || — логическое или

  • !, -(минус) — логическое не

А также >,>=, <,<=,== для спец. тегов (высота и ширина).

Так как мы передаем в бд объект сгенерированный из пользовательского ввода, будет не лишним ввести защиту от nosql инъекций.

const nosql_injection_regex = new RegExp(/[|]|$|:|{|}/gm) //[,],$,:,{,}

Примеры

//build_ast("forest&&height>=1920&&width>=1080")
//=>
{
   "$and":[
      {
         "$and":[
            {"tags":"forest"},
            {"height":{"$gte":1920}}
         ]
      },
      {"width":{"$gte":1080}}
   ]
}

//build_ast("forest(wi(nter) || nice!")
//=>
{
  "$or": [
    {
      "tags": "forest(wi(nter)"
    },
    {
      "tags": "nice!"
    }
  ]
}

build_ast("(a||b)&&(-a||-b")
=>
{
  "$and": [
    {
      "$or": [
        {
          "tags": "a"
        },
        {
          "tags": "b"
        }
      ]
    },
    {
      "$or": [
        {
          "$nor": [
            {
              "tags": "a"
            }
          ]
        },
        {
          "$nor": [
            {
              "tags": "b"
            }
          ]
        }
      ]
    }
  ]
}

Вместо Not используется nor, на результат не влияет, но фиксит какую-то проблему с not в монгодб.

Поиск изображений с похожими тегами

Поиск изображений, у которых наибольшее количество общих тегов c изображением, по которому ищем. Изображения сортируются по количеству общих тегов.

Чем больше тегов у изображения и чем более точно они его описывают, тем лучше будет работать данный вид поиска. 

async function get_images_with_similar_tags(image_id: number, limit: number) {
    const target_tags = (await get_image_tags_by_id(image_id))?.tags
    if (!target_tags) {
        return []
    }
    const x = IMAGES_COLLECTION.aggregate([
        { $unwind: "$tags" },
        { $match: { tags: { $in: target_tags } } },
        { $group: { _id: { id: "$id", height: "$height", width: "$width" }, count: { $sum: 1 } } },
        { $sort: { count: -1 } },
        { $limit: limit }
    ])
    return x.toArray()
}

Результаты

Ambience

Стек — Node.js + Fastify + TypeScript (api gateway)

Возможности: выполнение запросов к нескольким микросервисам одновременно. Например, при добавлении нового изображения через веб интерфейс, идет запрос на вычисление всех features в ambience, откуда в свою очередь посылаются запросы на отдельные микросервисы.

async function calculate_all_image_features(image_id: number, image_buffer: Buffer) {
    return Promise.allSettled([
        calculate_akaze_features(image_id, image_buffer),
        calculate_nn_features(image_id, image_buffer),
        calculate_hist_features(image_id, image_buffer),
        calculate_phash_features(image_id, image_buffer),
    ])
}

проксирование запросов до нужного микросервиса, т.е из scenery можно достучаться до любого хендлера любого микросервиса. 

const nn_routes = ['/nn_get_similar_images_by_image_buffer', '/nn_get_similar_images_by_text',
    '/nn_get_similar_images_by_id', '/calculate_nn_features', '/delete_nn_features', '/nn_get_image_tags_by_image_buffer']
nn_routes.forEach((r) => server.post(r, async (_req, res) => {
    try {
        res.from(combineURLs(config.nn_microservice_url,r))
    } catch (err) {
        res.status(500).send('NN microservice is down')
    }
}))

Для проксирования используется fastify-reply-from, который использует undici, http 1.1 клиент для node.js. undici гораздо быстрее, чем стандартный модуль http.

Стек микросервисов по работе с поиском изображений: Python + SQLite + FastAPI  

SQLite используется только для холодного хранения данных, весь поиск осуществляется с помощью специальных библиотек.

phash и akaze используют faiss IVF. rgb_hist использует faiss L1 Flat. NN использует hnswlib.

Далее пойдет описание микросервисов, которые используют методы поиска изображений из моей предыдущей статьи, с доработками и улучшениями.

phash

Задача микросервиса: поиск по phash (устойчив к ресайзу, в основном нужен для обнаружения одинаковых фото разного размера, неустойчив к кропу)

В предыдущей статье я использовал библиотеку ImageHash. Посмотрим, как работает функция phash.

def phash(image, hash_size=8, highfreq_factor=4):
	"""
	Perceptual Hash computation.
	Implementation follows http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html
	@image must be a PIL instance.
	"""
	if hash_size < 2:
		raise ValueError("Hash size must be greater than or equal to 2")

	import scipy.fftpack
	img_size = hash_size * highfreq_factor
	image = image.convert("L").resize((img_size, img_size), Image.ANTIALIAS)
	pixels = numpy.asarray(image)
	dct = scipy.fftpack.dct(scipy.fftpack.dct(pixels, axis=0), axis=1)
	dctlowfreq = dct[:hash_size, :hash_size]
	med = numpy.median(dctlowfreq)
	diff = dctlowfreq > med
	return ImageHash(diff)

Для тестов возьмем изображение 5919×3946 1.52 MB

Оригинальный код — 0.31 с

Как сделать python код быстрые? Выполнять код не в python: D

Используем Numba — JIT компилятор с nopython mode — код компилируется и выполняется вне python. Также сделаем так, чтобы на выходе мы получали не 256 булевых значения, а 32 uint8.

v1

@jit(nopython=True, cache=True)
def diff(dct_data, hash_size):
    dctlowfreq = dct_data[:hash_size, :hash_size]
    med = np.median(dctlowfreq)
    diff = dctlowfreq > med
    return diff.flatten()

def fast_phash(image, hash_size=16, highfreq_factor=4):
    img_size = hash_size * highfreq_factor
    image = image.convert("L").resize((img_size, img_size), Image.ANTIALIAS)
    pixels = np.asarray(image)
    dct_data = dct(dct(pixels, axis=0), axis=1)
    return diff(dct_data, hash_size)

@jit(nopython=True, cache=True)
def bit_list_to_32_uint8(bit_list_256):
    uint8_arr = []
    for i in range(32):
        bit_list = []
        for j in range(8):
            if(bit_list_256[i*8+j] == True):
                bit_list.append(1)
            else:
                bit_list.append(0)
        uint8_arr.append(bit_list_to_int(bit_list))
    return np.array(uint8_arr, dtype=np.uint8)

@jit(nopython=True, cache=True)
def bit_list_to_int(bitlist):
    out = 0
    for bit in bitlist:
         out = (out << 1) | bit
    return out

def get_phash(query_image):
    bit_list_256 = fast_phash(query_image)
    phash = bit_list_to_32_uint8(bit_list_256)
    return phash

v1 — 0.26 c

Заменим

def fast_phash(image, hash_size=16, highfreq_factor=4):
  img_size = hash_size * highfreq_factor
  image = image.convert("L").resize((img_size, img_size), Image.ANTIALIAS)
  pixels = np.asarray(image)
  dct_data = dct(dct(pixels, axis=0), axis=1)
  return diff(dct_data, hash_size)

на

def fast_phash(image, hash_size=16, highfreq_factor=4):
    img_size = hash_size * highfreq_factor
    image = cv2.resize(image, (img_size, img_size), interpolation=cv2.INTER_LINEAR
    dct_data = dct(dct(image, axis=0), axis=1)
    return diff(dct_data, hash_size)

v2 — 0.14 с

В данном примере ускорение незначительно, т.к в оригинальном коде уже используются сильно оптимизированные библиотеки (Pillow, scipy, numpy). Можно ускорять и дальше, например, ускорить ресайз используя pyvips, или ускорить DCT. Я не знаю насколько сильно влияет тип ресайза на силу хеша (устойчивость), но не думаю что очень сильно.

Чтобы быстрее вычислять cpu bound задачи, используем библиотеку joblib. Это очень простой способ распараллелить какую-нибудь задачу на питоне.

Для вычисления множества хешей (например, при массовом импорте изображений с помощью python скрипта), используем joblib. Задача выполняется быстрее практически в n раз, где n это количество ядер.

phashes = Parallel(n_jobs=-1, verbose=1)(delayed(calc_phash)(file_name) for file_name in batch)

rgb_hist

Задача: поиск изображений с похожей цветовой палитрой.

Практически ничего не менял, тот же поиск по гистограммам, только теперь в faiss flat L1, потому что faiss IVF не поддерживает метрики кроме L2 и IP.

Каждый бин гистограммы делим на количество пикселей в изображении, чтобы «уравнять» изображения с разным количеством пикселей.

def get_features(query_image):
    query_hist_combined = cv2.calcHist([query_image], [0, 1, 2], None, [16, 16, 16], [0, 256, 0, 256, 0, 256])
    query_hist_combined = query_hist_combined.flatten()
    query_hist_combined = query_hist_combined*10000000
    query_hist_combined = np.divide(query_hist_combined, query_image.shape[0]*query_image.shape[1], dtype=np.float32)
    return query_hist_combined

Результаты

akaze

Задача: поиск обрезанных версий изображений.

В прошлой статье я рассматривал SIFT/SURF/ORB и поиск брутфорсом.

Медленно ищется (Есть методы значительно ускоряющие поиск, но я не нашел понятного примера на python)

Примера я так и не нашел, поэтому написал свой. На этот раз использую AKAZE и ищу с помощью faiss ivf.

Дескриптор 1 ключевой точки (keypoint) весит 61 байт. (61 uint8). Будем искать 256 точек, тем самым 1 изображение будет описываться 15616 байтами. Число точек можно увеличить, но это также увеличит требования к оперативной памяти, т.к все дескрипторы этих точек нужно хранить в RAM для быстрого поиска.

Для того чтобы получить 256 наиболее «хороших» точек, сортируем по полю response. Чем выше значение response, тем качественнее точка (т.е более устойчива к изменениям).

kps1 = AKAZE.detect(img1,None)
kps1 = sorted(kps1, key = lambda x:x.response,reverse=True)[:256]

256 наиболее 256 наиболее «хороших» точек

Видно, что точки сосредоточены в 1 области, нам бы хотелось, чтобы точки были расположены более рассредоточено.

Поделим изображение на 4 квадранта и найдем 64 лучших точки в каждом квадранте. Сделать это легко, каждая точка имеет координаты x и y, по ним определяем квадрант.

64 лучших точки в каждом квадранте 64 лучших точки в каждом квадранте

Уже лучше, но все равно, точки разбросаны не так равномерно как хотелось бы. Введем ограничение — в радиусе 40 пикселей может быть не более 3 точек.

ограничение в 40 пикселейограничение в 40 пикселей

Вычислим дескрипторы этих точек и сохраним в sqlite.

Поиск

Алгоритм поиска.

Загружаем наши дескрипторы в IVF, предварительно его натренировав. Извлекаем точки из изображения по которому ищем и вычисляем дескрипторы. С помощью IVF к каждому из 256 дескрипторов находим ближайший по расстоянию Хэмминга. У каждого дескриптора есть ID, по которому можно определить из какого он изображения. Будем считать, что одинаковых дескрипторов практически не бывает (это неправда). Дескрипторы с расстоянием Хэмминга > 65 не рассматриваем.

Для того чтобы изображение считалось дубликатом необходимо выполнение хотя бы одного из этих условий:

  • 2 и более дескриптора с расстоянием Хэмминга <= 5

  • 4 и более дескриптора с расстоянием Хэмминга <= 10

  • 6 и более дескрипторов с расстоянием Хэмминга <= 15

  • 8 и более дескрипторов с расстоянием Хэмминга <= 32

  • количество дескрипторов с расстоянием Хэмминга <=64 больше 10 и их количество в >= 3 раза больше, чем медианное значение

Проверки нужны для того, чтобы избежать ложноположительных результатов, т.к в реальности в двух совершенно разных изображениях могут оказаться точки, дескрипторы которых равны, либо очень близки по расстоянию Хэмминга.

То же самое, но в коде

def median(lst):
    list_length = len(lst)
    index = (list_length - 1) // 2
    if (list_length % 2):
        return lst[index][1]
    else:
        return (lst[index][1] + lst[index + 1][1])/2.0


def _akaze_reverse_search(D, I, file_name):
    levels_threshold = [2, 4, 6, 10]
    levels = [{}, {}, {}, {}]
    all_points = {}
    for i in range(len(I)):
        point_dist = D[i]
        if(point_dist > 65):
            continue
        point_id = I[i]
        image_id = point_id_to_image_id_map[point_id]
        if image_id == file_name:  # skip original image
            continue
        if point_dist <= 5:
            levels[0][image_id] = levels[0].get(image_id, 0)+1
        if point_dist <= 10:
            levels[1][image_id] = levels[1].get(image_id, 0)+1
        if point_dist <= 15:
            levels[2][image_id] = levels[2].get(image_id, 0)+1
        if point_dist <= 32:
            levels[3][image_id] = levels[3].get(image_id, 0)+1

        all_points[image_id] = all_points.get(image_id, 0)+1

    for i in range(4):
        if(len(levels[i]) > 0):
            sorted_levels = sorted(levels[i].items(), key=lambda item: item[1])
            if sorted_levels[-1][1] >= levels_threshold[i]:
                print({"data": sorted_levels[-1], "level": i})
                return [sorted_levels[-1][0]]

    if len(all_points) >= 2:
        sorted_all_points = sorted(all_points.items(), key=lambda item: item[1])
        median_number_of_points = median(sorted_all_points)
        if sorted_all_points[-1][1] >= 10:
            if((sorted_all_points[-1][1]/median_number_of_points) >= 3):
                print(sorted_all_points[-1])
                return [sorted_all_points[-1][0]]
    return []

Результаты

nn

Задача: семантический поиск, поиск похожих изображений, автотегирование

Семантический поиск, поиск похожих изображений: все так же, как и в предыдущей статье, но в этот раз вместо CLIP ViT-B/32 используется ViT-B/16

Автотегирование: Resnet50 для определения категории картинки и Resnet18 для определения атрибутов сцены и indoor/outdoor. Pre-trained на датасете Places365. Точность отставляет желать лучшего, но это хоть какая-то автоматизация.

Примеры семантического поиска

Я не устаю поражаться, насколько много всего знает clip. По запросам pale blue dot/a photo made by voyager/voyager-1, первое фото — воссозданная в blender 8K версия знаменитой Pale Blue Dot, фотографии Земли, сделанной космическим зондом «Вояджер-1».

a photo made by voyagera photo made by voyagersand dunessand dunesa photo of forest and rivera photo of forest and river

Примеры поиска похожих изображений

Первое фото — фото по которому идет поиск

image-loader.svgimage-loader.svg

Примеры тегов

['far-away horizon', 'natural', 'natural light', 'outdoor', 'iceberg', 'ocean', 'boating', 'open area']['far-away horizon', 'natural', 'natural light', 'outdoor', 'iceberg', 'ocean', 'boating', 'open area']['skyscraper', 'vertical components', 'downtown', 'man-made', 'canal/urban', 'open area', 'outdoor', 'natural light']['skyscraper', 'vertical components', 'downtown', 'man-made', 'canal/urban', 'open area', 'outdoor', 'natural light']['natural', 'open area', 'foliage', 'outdoor', 'no horizon', 'natural light', 'vegetation', 'waterfall', 'trees', 'rainforest', 'leaves']['natural', 'open area', 'foliage', 'outdoor', 'no horizon', 'natural light', 'vegetation', 'waterfall', 'trees', 'rainforest', 'leaves']

IPFS

IPFS (Inter Planetary File system) — это контентно-адресуемая p2p файлообменная сеть. Будем использовать её для децентрализованного хранения/раздачи картинок.

image-loader.svg

Сделаем на сайте тумблер, при активации которого все ссылки типа https://example.com/images/1.jpg преобразовываются в ipfs ссылки.

Обычно, ссылки на файлы выглядят так: /ipfs/, где CID это идентификатор контента (Content Identifier). То есть, если мы хотим, чтобы клиент мог скачать контент через ipfs, ему нужно отдать ipfs хеши изображений, которые надо будет хранить в бд, обновлять при обновлении изображений и.т.д. Не очень удобно. Эту проблему можно элегантно решить с помощью IPNS. IPNS (InterPlanetary Name System) — это децентрализованная версия dns для ipfs. Позволяет использовать адрес, который указывает на хеш файла (папки). Можно поменять хеш, на который ссылается адрес, без изменения адреса. Так мы превратили content-based адресацию в address-based. IPNS довольно сложно запомнить /ipns/k51qzi5uqu5dhlil169t1my3wmb5zzwugvtjcq6duc2bhgcbjsbc77wmdqwbsh, поэтому используем DNSLink — ipfs умеет подтягивать ipns адрес из TXT записи домена.

104305721710f441aa98013a7408affb.JPG

Теперь ссылка на файл выглядит так http://127.0.0.1:8080/ipns/ipns.scenery.cx/thumbnails/71.jpg (Как можно догадаться, работает только после установки IPFS клиента).

Интересный факт: ipfs клиент 30 минут раздает файлы которые только что скачал. Получается что-то наподобие distributed CDN.

crud_file_server

Используя IPFS http api добавляем полученные изображения в ipfs/ipns. Может добавлять изображения полученные по http, либо синхронизировать локальную папку с ipfs.

Image tools

Различные полезные утилиты для облегчения работы с изображениями.

Yandex reverse image search

Используем поиск по изображению яндекса, чтобы найти изображение в большем размере. API я не нашел, зато нашел https://yandex.ru/legal/pictures_api/. Видимо какое-то закрытое апи все же есть. Мы будем просто парсить.

image-loader.svg7e258ba11b06e4a674fcaa56e3d13eae.JPG

Автоматически заменить старое изображение новым нельзя — довольно часто изображение с более высоким разрешением оказывается просто апскейлом оригинала, либо разрешение больше, а качество ниже. Поэтому сравнивать новое изображение со старым придется вручную. Обход rate-limit’а остается читателям для самостоятельного выполнения.

Border detection

Алгоритм для детекции рамок у изображений. Много ложно положительных результатов.

  1. Получаем цвет крайнего левого пикселя

  2. Вычисляем попиксельную разницу между нашей картинкой и левым крайнем пикселем

  3. «Усиляем» разницу

  4. Вычисляем bbox (максимальный прямоугольник, ненулевых пикселей)

  5. Чтобы исключить побольше ложноположительных результатов, считаем, что у изображения есть рамки только если они парные (т.е если есть полоса сверху, то должна быть полоса cнизу и.т.д)

Оригинальное изображение

e52a2039567c274d47165a4efc7b8ef9.jpg

Изображение после всех манипуляций

image-loader.svg

Полуавтоматическая детекция вотермарок

Идея достаточно примитивная — детектим текст на картинке, если текст есть, картинку удаляем (или не удаляем, а складываем распознанный текст и удаляем вручную, после проверки). Т.к датасет достаточно специфичный (пейзажи, обои, природа, атмосферные фото), то текста в картинках практически нет. Tesseract для задачи не подходит — текст разных шрифтов, разного качества. EasyOCR отлично подходит для нашей задачи, так как изначально разрабатывался для ocr в различных условиях (не только сканы различных документов, но и текст in the wild)

https://github.com/JaidedAI/EasyOCR

Что можно улучшить/Мысли/Идеи

Улучшить можно всё : D

Можно заменить phash (DCT) на что-нибудь новое, например на алгоритмы на базе ML (привет Apple NeuralHash). Целесообразность сомнительная — phash (DCT) и так отлично решает задачу поиска near-duplicate картинок и я сомневаюсь что ML-based алгоритмы обладают какими-то отличительными качествами (искать кропы они вряд ли смогут)

Можно заменить AKAZE на более продвинутые детекторы/дескрипторы, но это увеличит требования к производительности сервера.

Возможно, есть какая-то нейросеть, которая ищет похожие изображения лучше, чем CLIP ViT B/16. Было бы классно, если бы данная нейросеть могла дообучаться на новых данных, увеличивая точность поиска, в идеале полностью автоматически, без разметки новых данных. То же самое можно сказать и про автотегирование.

Можно заменить rgb гистограммы на что-то более компактное, т.к. сейчас вектор из 4096 значений на 60–70 процентов состоит из нулей, а хранить нули — это как-то не очень. (я пробовал использовать ANNS которые поддерживают sparse вектора, но там возникли какие-то проблемы). Сейчас rgb гистограммы не учитывают положение пикселей в изображении, а только их количество. Можно разбить изображения на блоки, найти гистограммы этих блоков и искать изображения у которых блоки максимально похожие. Эта штука называется local color histogram и по идее должна быть лучше, чем global color histogram (то что есть сейчас). Я экспериментировал с другими цветовыми пространствами (YUV, HSV, LAB), но результаты были хуже, чем RGB. Возможно, я просто неправильно их «приготовил», нужны дополнительные тесты.

Можно использовать jpegXL, т.к он позволяет сократить размер изображений, но пока из коробки, он не поддерживается ни одним браузером.

Автоматический майнинг изображений

Для автоматического майнинга изображений нужен модуль для вычисления степени соответствия картинки датасету. Скорее всего, это можно сделать, используя вектора сгенерированные в nn, создав несколько кластеров с помощью kmeans и считать что изображение нам подходит, если расстояние между новой картинкой и каким-то кластером меньше определенного порогового значения. Эту идею я пока не проверял.

Также необходим алгоритм для определения визуального качества изображения, одного разрешения недостаточно. Пока оценивать качество приходится вручную. Этот модуль возможно один из самых важных: он улучшит систему на всех уровнях, от дедупликации (можно будет оставлять версию изображения с лучшим качеством, а не ту у которой больше пикселей, как работает сейчас) до автоматического майнинга.

На ум приходит несколько стратегий:

  • Скан интернета с помощью своего поискового робота (сложно реализовать технически)

  • Ручной поиск источников изображений (определенные сайты/сабреддиты) и их последующий периодический парсинг

  • Использование сервисов по типу Yandex reverse image search. Там есть секция похожих изображений, её можно спарсить и сделать что-то на подобии breadth-first search: найдем похожие изображения к тем, что уже есть в датасете, затем найдем похожие к похожим, и так далее

Долго думал над тем, как закончить эту статью. Закончу вот такой мыслью. Для меня web 3.0 — это автономные самообучающиеся сервисы, где клиенты могут участвовать в раздаче контента.

https://github.com/qwertyforce/scenery
https://github.com/qwertyforce/ambience
scenery.cx

© Habrahabr.ru