PikabuDev

Всем привет!

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

1. Самое важное изменение - мы более не сжимаем видео и аудио потоки, если заливаемый видео файл весит меньше 4 МБ. Т.е. то качество, что на вход, мы сохраняем и на выход если размер файла не превышает 4 МБ.

2. Добавил новый кодек, в который мы конвертируем видео на выход - AV1. Вот с ним больше всего проблем пока что. Он хорошо сжимает видео и при этом сохраняет качество (эффективнее на 20-40%, чем другие наши кодеки), но после релиза у пользователей начали всплывать различные проблемы с ним, в основном на слабых процессорах мобильных устройств, в Edge и Yandex.Браузере. В итоге пока что он работает только на десктопных браузерах: Chrome 100+, Opera 90+, FireFox 100+. В будущем будем расширять поддержку.

3. Увеличили максимальный размер картинки выходного видео с 720px по ширине до 1920px. Т.е. теперь можно заливать, например, скринкасты своего рабочего стола и не будет все размылено за счет уменьшения по ширине.

4. Теперь мы конвертируем видео только в те форматы, в которые имеет смыл конвертировать. Например, вы можете залить видео файл в H.264 кодеке и контейнере mp4, и Пикабу решит, что это видео слишком "жирное" и нужно бы его сконвертировать в webm (VP9) и mp4 (AV1) форматы. В итоге ваше видео будет существовать в 3 форматах, и каждый клиент (браузер, приложения и тд) загружает тот формат, который поддерживает. Как правило при одинаковом качестве webm (vp9) весит меньше, чем mp4 (h.264), а mp4 (av1) весит меньше webm. таким образом клиенты, которые поддерживают av1 будут меньше тратить трафика при просмотре видео на Пикабу и, как следствие, быстрее загружать его.

5. Небольшое изменение - мы стали стирать мета информацию в видео файлах и писать туда в поле комментария "pikabu.ru". Зачем? Да просто так :D Но стираем для того, чтобы не заливали на Пикабу всякие "шуточки", политические лозунги и прочее вписанные в мета параметры видео файла.

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

Итак, как же заливать на Пикабу видео, чтобы оно сохранило оригинальное качество?

Самый лучший вариант - заливать кодек H.264 в контейнере mp4 и чтобы видео файл весил менее 4 МБ, не был обрезан в редакторе поста и размер картинки не превышал 1920px по ширине или высоте. В этом случае то, что залили, то и будет показано пользователям без каких-либо конвертаций видео потока.

Любой другой кодек будет вынуждать Пикабу делать конвертацию. Но конвертация не равно сжатие. Так что и в другом кодеке если ваше видео весит до 4МБ Пикабу более-менее сохранит качество, просто тут уже будет процесс перекодирования видео в другой кодек, а это так или иначе скажется на качестве чуть-чуть.

Как получить H.264, если "у меня лапки" и я хочу сохранить качество видео?

Лучше всего найти друга-компьютерщика и за бутылку пива попросить научить такое делать. Если таких друзей вам не нужно, то в сети очень много различных видео редакторов, которые способны делать переконвератции, но без друга вы уже сами как-то обучитесь. Однако если вы знаете как запускать программы из командной строки, то мы рекомендуем самый популярный бинарник для конвертации - ffmpeg.  С помощью него можно подобрать самые оптимальные критерии, при котором ваше видео будет до 4 МБ, в хорошем качестве и в кодеке H.264)

В этом посте расскажу как устроена одна из самых глючных функций Пикабу - скрытие просмотренных постов. У этой функции богатая история проб и ошибок, 100500 жалоб пользователей, много попыток замены её и, как результат, достаточно интересное последнее техническое решение о котором в данном посте пойдет речь) Постараюсь все рассказать популярным языком, а в конце поста будет ссылка на кое-какой инструмент, который покажет визуально как вы смотрите Пикабу) Но для начала коротко расскажу о самой функции.

Когда зарегистрированный пользователь листает ленты постов мы фиксируем факт просмотра каждого поста и сохраняем эту информацию на сервере. Затем, при открытии любой основной ленты (Горячее, Лучшее, Свежее, Подписки и тд), мы на лету фильтруем весь список постов этой ленты и оставляем только те посты, что пользователь ещё не видел. Таким образом пользователь один раз увидев пост на Пикабу больше его не должен видеть тут) “Да что вы  такое говорите!” - сказали почти все, кто пользовались функцией скрытия просмотренного :D Попробуем разобрать какие есть проблемы у системы скрытия просмотренного.

Проблемы

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

В этом посте будем рассматривать самую интересную проблему - как хранить просмотры миллионов постов для миллионов пользователей и при этом за миллисекунды фильтровать большие массивы постов каждой ленты. Например, некий пользователь admin за 12 лет на Пикабу посмотрел в общей сложности 7 млн постов и сейчас открывает ленту лучшего за все время, где 13 тыс постов. Серверу нужно как-то моментально найти пересечение двух множеств из 7 млн и 13 тыс идентификаторов постов, чтобы исключить из ленты те посты, что пользователь уже видел. Задача нетривиальная для многих NoSQL БД, и уж тем более для всяких RDBMS а-ля MySQL. Так как время генерации страницы должно стремиться к нулю, то делать тяжелые запросы - не вариант, нужно искать быстрые решения.

Что мы пробовали ранее

Больше всего решений мы перепробовали на хранении в Redis некого буфера из 12 тыс последних просмотренных постов. Причем размер буфера все время рос: вначале был вроде 6 тыс, затем 8, 10, и вот остановились на 12 тыс. Изначально мы не ставили цель хранить просмотры постоянно, а хотя бы скрывать недавно просмотренные посты и для этого хорошо подходит Redis. В итоге последняя наша реализация на Redis была через Redis списки: это по сути обычный список записей в БД под общим ключом, который можно дополнять слева или справа, обрезать, и вытворять с ним многое чего веселого.

Однако буфер из 12 тыс последних просмотренных не хватал пользователям и многие сообщали, что видели посты повторно. Далее увеличивать размер буфера - путь в никуда. Решили, что нужно попробовать переводить систему просмотренных постов с ограниченного буфера во временном хранилище на хранение всех просмотров в постоянное хранилище. Для такого хранения рассматривали те БД, что есть в арсенале: Cassandra, MySQL, ElasticSearch, ClickHouse. Попробовав разные вариант остановились на Kafka + ClickHouse + Redis и какое-то время система просмотров работала на такой схеме. Однако в бою постепенно начали всплывать проблемы с такой схемой (нагрузка, скорость выполнения запросов, нестабильность кластера), которые мы не могли решить тот момент, и мы приняли решение попробовать что другое, менее ресурсоемкое и более заточенное под задачу)

Новая система хранения просмотров

Мы решили так: будем хранить для каждого пользователя по 1 биту для каждого поста, который он видел или не видел! Т.е. если, условно, на Пикабу 10 млн постов, то для каждого пользователя мы будем хранить 10 млн бит o___O.

Абсурд! Зачем хранить где-то биты для всех постов, которые пользователь даже не видел ещё?

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

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

Чанки

Но 10 млн бит - это без малого 1.2 МБ данных и список состояний для очень большого числа постов, к тому же список постоянно растет. В 90% случаев нам нужно узнать состояния просмотрен или нет постов за определенный период времени. Например, открываем Горячее или Свежее, и там посты за последнюю неделю где-то, это примерно 13 тыс постов. Получается нет смысла загружать все биты сразу и поэтому мы их делим на куски равной длины (чанки, от англ. chunk).

Но какую длину чанков выбрать? Изначально мы взяли круглое число - 100 тыс бит на 1 чанк (это примерно полтора месяца постов). Однако потом выбрали размер чанка равный 131072 бит.

Если кто-то понял что это за число - знай, ты красавчик! Для всех остальных - это число степени двойки (2 в 17й степени, т.н. POT число). Но зачем? Все просто, из-за математической операции поиска номера чанка. Мы на Пикабу при разработке бэкенда стараемся все зацикленные операции с большими количеством итераций делать максимально оптимальным кодом, экономить на спичках, так сказать (но без фанатизма, только для больших циклов). Если бы размер чанка был 100 тыс бит, то чтобы определить в каком чанке лежит бит для поста №8518117 нам потребовалось сделать следующее:

chunk = ⌊8518117 / 100000⌋ = 85

Тут у нас 2 операции, деление с остатком и округление (⌊..⌋ - это символы округления вниз). Однако, если чанк будет иметь длину 2^17 бит, то поиск номера чанка будет значительно быстрее выполняться следующей одной супер быстрой операцией:

chunk = 8518117 >> 17 = 64

Тут мы применили побитовое смещение на 17, что равносильно делению на 131072 и отсечению дробной части.

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

first_story_id = chunk << 17 = 64 << 17 = 8388608

“Шо, опять?”) Да, снова побитовая операция, и все благодаря тому, что не от балды выбрали размер чанка. Операция смещения бит влево на 17 равносильна умножению числа на 131072, только быстрее чем обычная операция умножения)

Зная номер поста для первого бита внутри чанка мы легко можем посчитать номер бита для нужного нам поста:

bit_index = 8518117 - first_story_id = 129509

Но так как бит зачитать вот прямо так из другой кучи бит не каждый может (php не может), то нам нужно для начала получить байт в котором этот бит расположен следующей математикой

byte_index = bit_index >> 3 = 129509 >> 3 = 16188

“Шо, опять?” Все верно, тут мы тоже применили смещение, так как каждый школьник знает, что в байте хранится 8 бит, а число 8 - это тоже POT, 2 в 3й степени)

Мы знаем номер байта, в котором хранится нужный нам бит. Осталось зачитать этот байт как число и проверить состояние бита:

viewed = byte & (bit_index - (byte_index << 3))

Если viewed будет равен единице, значит пост с номером 8518117 когда-то был просмотрен пользователем :) И вот такую математику мы выполняем для всех постов в любой ленте, т.е. где-то цикл по 13 тыс постов при каждом открытии ленты.

Один чанк имеет 131072 бит, это 16384 байт. Так как чанк содержит последовательные биты просмотров (1) или наоборот не просмотров (0), то он идеально сжимается тем же gzip и весит всего 200-800 байт в среднем у пользователей. На загрузку одной ленты как правило достаточно загрузить 1 чанк, редко бывает, когда нужно загружать 2 и более чанков)

Чанки мы сохраняем в Aerospike. У нас их два для этого дела: горячий на ssd дисках для трех последних чанков (это примерно последние 400 тыс постов) и холодный на hdd дисках, где все остальные чанки.

Сейчас новая система скрытия просмотренных работает на связке Redis + Aerospike. В Redis записываем как и раньше временный буфер из 12 тыс последних просмотренных постов, а в Aerospike записываем уже на постоянное хранение. Зачем нам две технологии? Во-первых Redis позволяет не сразу записывать в чанки флаги, а делать 1 запись на каждые 5-10 просмотров. Это снижает вероятность такой проблемы, как race condition (состояние гонки), когда два параллельных процесса пытаются обновить одну бедненькую запись чанка. Во-вторых банальный fail over, если из-за аварии упадет Aerospike, то временно Redis будет хотя бы 12 тыс последних просмотров поддерживать, и наоборот.

На данный момент каждый пользователь имеет всего 65 чанков и самый заполненный - это 64й чанк) На прошлой неделе стартовал у всех 65 чанк, так что он еще совсем пустой.

Новую систему на чанках мы зарелизили всего пару месяцев назад, поэтому в чанках мы храним лишь информацию, что пользователи видели за эти последние пару месяцев.

Как вы смотрите Пикабу?

Когда мы тестировали новую систему хранения просмотренных постов мы написали к ней визуализатор чанков. Этот визуализатор выводит в картинку размером 800x660 пикселей все 131 тыс бит одного чанка. Если бит установлен в 1, то пиксель синий, иначе пиксель серый или белый. На визуализаторе свежих чанков можно увидеть какой объем постов вы видели, а какой так и не увидели. Т.е. если много серых точек - это все те мемчики, что вы пропустили) Если подряд идут много синих линий, значит вы смотрели свежее, так как система зафиксировала просмотры подряд идущих постов. Например, вот как смотрит Пикабу нейкий пользователь 0x00:

Как видно много горизонтальных синих линий, значит 0x00 часто зависает в свежем.

А вот к примеру как выглядит чанк рандомного автора из горячего (не буду раскрывать кто он):

Сразу понятно, что пользователь редко в свежее заходит, да и вообще вероятно смотрит только горячее, лучшее или подписки свои. Также видно, что у него были пробелы в посещении сайта )

Увидеть свои чанки и то, как плотно вы смотрите Пикабу можно вот тут (лучше с ПК): https://pikabu.ru/page/misc/chunks/

Ссылка доступна только если есть авторизация на сайте)

В этом посте я расскажу в деталях как устроен поиск похожих постов на Пикабу и почему баянометр иногда молчит :)

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

Текущая технология поиска баянов была разработана нами в запущена в бой в октябре 2014 года. Это была вторая версия баянопоиска и её целью было улучшить качество и скорость поиска похожих постов. 

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

ПОИСК ВИДЕО

Модуль поиска похожего видео работает только для видео, добавленных с внешних видео-хостингов, таких как youtube, vimeo, coub и пр. Поиск выполняется по внешнему идентификатору, который есть в URL к видео. Например, в следующем URL https://www.youtube.com/watch?v=dQw4w9WgXcQ идентификатором будет dQw4w9WgXcQ. Таким образом поиск похожих постов для видео из внешних видео-хостингов самый примитивный и ищет по сути посты, в которых добавили такую же ссылку на видео. Но если пользователь заливает видео файл (mp4, webm и пр), то тут уже другая песня и работает более сложный поиск по картинке, который мы разберем чуть ниже.

Исходя из рассказанного не сложно догадаться, что если добавить на Пикабу видео с youtube и затем попробовать такое же видео добавить с vimeo или просто залить как mp4 файл, то баянопоиск его никак не найдет сходства, так как у vimeo будет другой идентификатор у видео, а mp4 файл будет искаться другим способом.

Немного статистики по этому виду поиска: на текущий момент у нас в базе 932 тыс идентификаторов видео внешних хостингов, из них youtube - 90%, coub - 7.8%, vimeo - 0.7%, rutube и vk по 0.5%, liveleak всего 0.1%.

ПОИСК ТЕКСТА

Поиск по тексту посложнее и интереснее, почти как оргия с кучей фильтров) Основная сложность такого поиска - быстро найти сходство между одним текстом и миллионами других в базе данных. Подкованные в разработке ребята скажут, тут можно обычный LIKE использовать, либо можно Full-Text Search, Sphinx, ElasticSearch и тд. Но не все так просто. Одно дело искать строку среди разных текстов, а другое дело искать сходство текста с другими текстами. Ведь автор поста мог написать абзац своего текста, затем вставить абзац скопированного анекдота и поиск баянов должен будет найти не постил ли кто-нибудь уже такой анекдот. Также не забываем про объемы поиска, которые постоянно растут (сейчас более 8 млн постов), а требование стоит в моментальном поиске в момент набора текста.

Плотно покурив статьи разных умных гиков и глубоко погрузившись в пучину алгоритмов неточного поиска текстов было решено написать свой крутой велосипед)

Для объяснения принципа работы этого велосипеда возьмем следующую короткую панграмму с небольшим текстом:

Эй, жлоб! Где туз? Прячь юных съёмщиц в шкаф. Не судите строго на pikabu.

Шаг 1 - нормализация

Первым делом баянопоиск нормализует текст для русского языка: переведет все в нижний регистр символов, заменит буквы "ё" на "е" (а также "ў" на "y", "i" на "и"), удалит символы троеточия "…", приведет все дробные числа к единому формату (запятая вместо точки: 2.15 -> 2,15). Затем из текста удаляются замаскированные маты, типа "с@ка", "ебл#н", и цифры с буквенными наращениями, например 2-x, 3мя, 101-й.

В нашем случае в тексте изменится только регистр символов и буква "ё" в слове "съёмщиц":

эй, жлоб! где туз? прячь юных съемщиц в шкаф. не судите строго на pikabu.

Шаг 2 - удаление шаблонных фраз

На Пикабу пользователи часто в постах указывают одни и те же фразы, что в итоге приводит к бессмысленным результатам поиска, когда находятся сотни постов с такой фразой. Примеры фраз: "коммент для минусов внутри" (старички на Пикабу всплакнули, да?), "благодарю за внимание", "баянодетектор молчал". Или вот последнюю фразу что добавляли недавно: "источник - телеграм канал плохой шофер".

Удаление немного хитрое, оно учитывает разные варианты написания. Например, для фразы "взято с vk" будут удалены также варианты "взято из вконтакте", "взято из вк", "взято c vkontakte" и тд.

В нашем тексте есть шаблонная фраза "не судите строго", поэтому после её удаления текст станет следующим:

эй, жлоб! где туз? прячь юных съемщиц в шкаф. на pikabu.

Шаг 3 - токенизация

Токенизация - это по сути разбиение текста на отдельные независимые кусочки (термы), каждый из которых является минимальным самостоятельным фрагментом текста. Ай, проще это назвать разбиением текста на предложения и отдельные слова :D Понавыдумывали умных слов тут.

Мы бежим по всему тексту, ищем пунктуацию и принудительные переносы строк, отдельно стоящие слова, и затем разделяем текст на отдельные предложения (токены).

В нашем случае получится 4 токена:

- эй жлоб

- где туз

- прячь юных съемщиц в шкаф

- на pikabu

Шаг 4 - удаление стоп-слов

В каждом токене мы удаляем из текста так называемые стоп-слова. Так принято называть слова, в которых нет особой пользы при поиске. У Пикабу свой словарь таких слов и в нем сейчас 576 слов. Помимо общепринятых стоп-слов, типа "моя", "никуда", "однако", "через" и тд, в наш словарь мы включили и популярные маты с разным вариантом их написания :D Да-да, особо смысла искать маты нет, так как даже в анекдотах их кто-то маскирует, кто-то заменяет на другие слова, кто-то заменят другими матами. Также к стоп-словам мы отнесли pikabu и старое его название - pickaboo.

После удаления стоп-слов наш текст примет следующий вид (пропали "где", "в", "на" и "pikabu"):

эй жлоб // туз // прячь юных съемщиц шкаф

знаком "//" я показал разделение на токены. Как видно, у нас минус 1 токен, так как он целиком был удален.

Шаг 5 - словарь синонимов

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

Ну что, давайте посмотрим на что наш текст будет похож после этого шага:

эй жлоб // аристократ // прячь юных съемщиц шкап

Да, тут можно посмеяться, но слово "туз" имеет синоним "аристократ" :D А слово "шкаф" заменено на более древнее "шкап" (мы в разработке Пикабу знаем толк в извращениях :) ).

Шаг 6 - стемминг

Стемминг - это процесс удаления окончания и суфиксов у слов, чтобы осталась некая основа слова. Например, в русском языке слово "работа" может иметь много форм: работой, работал, работ, работе, работу и тд. Так вот стемминг все эти формы приведет к основе - работ.

После стемминга наш текст станет ещё краcивее:

э жлоб // аристократ // пряч юн съемщиц шкап

Шаг 7 - замена букв

Чтобы убрать различия в написании слов с гласными "о"/"а" и "е"/"и", мы все буквы "а" и "и" заменяем "о" и "е". Тем самым что автор напишет "присосался", что "пресасался" - для баянопоиска это будет одно и то же слово "пресосолся" :D

Ну что, взглянем на текст сейчас после этого шага:

э жлоб // орестокрот // пряч юн съемщец шкоп

Красота)

Шаг 8 - сортировка токенов

У нас в примере всего 3 токена осталось, но в реальности часто посты имеют большие тексты и там по 100-500 токенов. Так много токенов нам не получится искать, накладно. Поэтому мы должны выбрать токены самые значимые для поиска. Для этого токены делятся на 4 группы:

1. ничтожные токены, в которых 1 слово

2. слабые токены, в которых меньше 5 слов.

3. нормальные токены, от 5 до 16 слов.

4. сильные токены, от 16 и более слов.

Для нас самые привлекательные - нормальные токены, так как они и не жирные и не скудные. Поэтому мы сортируем так, вначале идут нормальные, затем сильные и в конце слабые токены. Ничтожные мы используем только в том случае, если других токенов у нас нет или если в этом токене URL (ссылка на что-нибудь).

Итого для поиска мы будем использовать следующие два токена:

1. пряч юн съемщец шкоп

2. э жлоб

Шаг 9 - расчет хэшей для токенов

Хэш - это представление любой информации в виде какой-то строки с всегда одинаковой длиной. Саму функцию хэша рассказывать не буду, там много всякий сложной математики. Но особенность нашего хэша в том, что мы для кажого слова внутри токена вычисляем некую контрольную сумму, затем сортируем по ней все слова внутри токена и затем берем лишь 5 первых слов и уже по ним финально вычисляем итоговый хэш как строку из 32 символов. Так что порядок слов не имеет значения внури токена: что маша мыла раму, что рама мыла машу.

Итого, для наших двух токенов будут следующие хэши:

1. 77a4bf0983fad218064fb2d36911c71d

2. 7b9758f810f00cdf169e2810e56127fe

Шаг 10 - поиск токенов в БД и сравнение постов

Каждый пост при добавлении на сайте проходит процедуру регистрации в базе данных баянопоиска. Так что каждый текст каждого поста проходит все эти 9 шагов и на выходе получаются токены, которые мы сохраняем в базу. Сейчас в базе насчитывается 34 миллиона токенов и вот по ним мы и ищем токены каждого нового текста из черновиков постов)

Если мы нашли токены в БД, то рано радоваться, ещё нет гарантии, что в том посте, где были найдены такие же токены, на самом деле текст совпадает с искомым. Мы выгружаем тексты постов, которые были найдены по токенам, и сравниваем уже более тщательно: сравниваем статистику количества одинаковых слов и вычисляем наибольшую общую подстроку . Немного математики с полученными данными для расчета релевантности (процент сходства текстов) и вуаля! Мы нашли баяны и показали на какой % тексты совпадают) Посты с релевантностью меньше 30% мы откидываем, так как это погрешности поиска.

Итого, основная фишка нашего поиска по текстам - это создать токены, по которым мы быстро можем найти посты с похожими текстами, а далее мы уже более плотно сравниваем тексты найденных постов с искомым текстом, чтобы точно определить % схожести и отбросить, если ложноположительный результат поиска был) Конечно, можно найти 100500 причин назвать этот велосипед извращением, особенно с учетом всех замечательных решений сегоднешнего дня, но

ПОИСК КАРТИНОК

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

Итак, какие задачи ставились перед новой версией баянопоиска по картинкам в 2014 году:

1. уметь искать отдельные независимые фрагменты картинок в длиннопостах. Ньюфаги вероятно не знают, а олдфаги позабыли, но раньше на Пикабу нельзя было добавлять несколько картинок в пост, только 1, и тогда были популярны т.н. длиннопосты, где вставлялась 1 длинная картинка с коллажем из разных фото. Вот пример ещё небольшого поста Стальные яйца. ;

2. уметь искать картинки перевернутые, отзеркаленные;

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

4. уметь искать картинки с измененным цветом;

5. искать быстро;

6. сортировать результаты поиска по релевантности.

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

Для объяснения как работает поиск по картинкам давайте возьмем для примера следующее изображение:

Шаг 1 - подготовка изображения

Если изображение имеет анимацию (gif) или вместо изображения используется видео (mp4, webm и др), то мы берем для дальнейшей работы только первый кадр.

Применяем фильтр рассеивания (Dispecle), который немного размажет границы (заметно по забору), но при этом сгладит шумы (пропали артефакты возле текста):

Шаг 2 - фрагментирование

Далее нам нужно разделить изображение на независимые фрагменты, каждый фрагмент мы будем искать отдельно. Для этого мы переводим изображение в черно-белый цвет (по сути оставляем только информацию о яркости каждого пикселя) и сжимаем по ширине до 128px самым быстрым алгоритмом масштабирования (тут качество не важно, важна скорость).

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

Анализ работает так:

- если в строке или колонке все пиксели имеют совсем небольшое количество уникальных значений яркостей (напомню, что картинка черно-белая, т.е. только яркости есть), то мы считаем эту строку пикселей бесполезной. Под такие строки попадают любые однородные фоны, на которых есть мелкий шум или текст.

- если статистика яркостей текущей строки на более чем 90% отличается от статистики яркостей предыдущей строки, то баянопоиск считает, что в данной строке начался новый фрагмент изображения.

На следующей иллюстрации желтыми полосками показано что баянпоиск посчитает бесполезным при построчном анализе, а голубыми - при анализе колонок.

Итак, мы нашли 1 полезный фрагмент, и откинули ненужные границы и тексты вокруг него. Однако поиск по базе данных мы будем делать все же по двум изображениям: оригинальному со всеми границами и текстами, и отдельным найденным фрагментом только с медведем.

Шаг 3 - оценка фрагментов

Баянопоиск умеет искать как по геометрии изображения, так и по статистике цветов. По геометрии имеет смысл искать, если у изображения есть перепады яркостей и их много, например, светлая и темные стороны чего-либо, а для поиска по цветам нужно наличие оных в картинке).

Приведу примеру двух плохих для поиска картинок:

В той, что скудная геометрия, компьютерное зрение может спутать со 100500 различными другими картинками, например, с флагом Польши, у него такая простая геометрия, линия сверху и линия снизу. В той, где скудная статистика цветов действительно всего несколько оттенков серого. В итоге баянопоиск на данном шаге решает, какие способы поиска имеет смысл использовать для каждого из фрагментов) Если изображение супер скудное по всем параметрам, то баянопоиск ищет только по геометрии и будь что будет :D

В нашем примере с медведем баянопоиск посчитает, что это изображение выгодно искать и по геометрии и по статистике цветов)

Шаг 4 - расчет геометрии изображений

Ещё это называют перцептивным хэшем. Принцип расчета очень прост: мы сжимаем изображение до супер маленького размера, например, до квадрата 16 на 16 пикселей, затем переводим все пиксели в черно-белую палитру, и сканируем пиксели по порядку с проверкой их по выбранному пороговому значению яркости. Если яркость пикселя ниже порога - это бит 0, если яркость выше порога - это бит 1. В итоге на изображение 16x16 у нас будет 256 бит, которые укладываются в 32 байта.

Баянопоиск рассчитывает таким образом два перцептивных хэша:  8x8 -  для грубого поиска и  24x24 - для точного. На следующем изображении показаны представления этих хэшей. Синий квадрат - это значит уровень яркости был выше порогового (бит 1), а белый квадрат - ниже (бит 0). Если изрядно выпить и прищуриться, то в этих квадратах можно увидеть мишку, сидящего на лавке :D

Итого, для грубого поиска по геометрии изображения мы рассчитали хэш длиной 8 * 8 = 64 бита, а для точного поиска - 24 * 24 = 576 бит.

Шаг 5 - расчет статистики цветов

Мы назвали этот способ расчета - гистограммный хэш, так как он строится на базе гистограммы (статистике цветов) изображения. Суть его проста: мы считаем для каждого канала RGB (Красного, Зеленого и Синего) статистику яркостей и получаем три гистограммы. Также мы строим гистограмму и для самого канала яркости (Luminance). Далее делаем квантование уровней, дискретизацию и получаем биты информации для каждой гистограммы) По сути так работает перевод аналогового сигнала в цифровой в телекоммуникациях.

Также как и в расчете геометрии мы делаем грубый и точный расчет. На следующем изображении показаны эти гистограммы (уже с квантованием по уровням):

Шаг 6 - поиск хэшей по базе

Увы, мы не можем искать по точному совпадению хэшей, так как минимальное отличие геометрии или гистограммы откинет потенциально похожий пост. Поэтому для поиска по базе данных мы применяем расчет расстояния Хэмминга , т.е. считаем количество отличающихся бит между искомым хэшем и теми, что в БД. Выглядит это примерно так:

01010101111000010101
01000101111100010101

В этих двух двоичных представлениях хэшей у нас отличаются только 2 бита, так что расстояние Хэмминга тут равно двум. Таким образом мы сравниваем искомый хэш с более чем 13 миллионами фрагментов изображений в БД.

Для ускорения поиска вначале мы ищем по грубым перцептивным и гистограммным хэшам. Для грубого перцептивного хэша допустимое количество отличающихся бит - 16, т.е. 25% от длины самого хэша (64 бит). Для гистограммного - 12 (18% от 64 бит).

Затем полученную выборку постов фильтруем уже точными хэшами, которые сложнее сравнить. Там для перцептивного хэша допустимое количество ошибок не превышает 140 бит (24%), а для гистограммного - 200 (39%).

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

Шаг 7 - финальная фильтрация

После поиска по базе данных мы выбрали большую пачку потенциально похожих постов. Теперь нам нужно ещё разок фильтровать эту пачку, чтобы откинуть посты, которые вероятно по ошибке (погрешности) система посчитала похожими. Для этого мы применяем ещё один хэш - DCT (дискретно косинусное преобразование) по изображению и по полученному результату строим снова перцептивный хэш. Сравниваем найденные по базе данных фрагменты с только что рассчитанным DCT-хэшем (тоже через расстояние Хэмминга), и если ошибок в битах не более чем 26%, то считаем, что это похожий пост.

Далее немного волшебной математики с разными показателями поиска и у нас на руках релевантрость для каждого найденного фрагмента. Отсеиваем все фрагменты, у которых релевантность ниже 18%, а все остальное показываем пользователю как возможные дубликаты)

ЭКСПЕРИМЕНТ С МЕДВЕДЕМ

Давайте проверим что будет, если к нашей картинке с медведем мы добавим смайлик, обрежем края немного, и перевернем на 180 градусов?

Геометрия изображения очень сильно поменялась, так как во-первых мы обрезали картинку, во-вторых перевернули. На следующей иллюстрации красным я подсветил отличия при сравнении перцептивных хэшей этих двух картинок. Отличий слишком много, поэтому поиск по перцептивному хэшу не дал результат:

А вот статистика цветов практически не поменялась и баянопоиск посчитал, что по гистограммному сравнению картинки равны на 80%!

Немного математики с DCT-хэшем и остальными результатами и итоговый вердикт баянопоиска - картинки схожи на 43%!

Теперь вы чуть больше знаете о том, как Пикабу ищет баяны. Надеюсь было интересно. Если будут вопрос - смело задавайте в комментах.

Немного о планах. Мы планируем попробовать заменить баянопоиск на новую версию, уже с ML (машинное обучение, нейронные сети). Но пока что ещё точно не знаем получится ли или нет, но если получится, то постараемся рассказать и о принципах его работы)