shiru8bit

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

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

Потратил ещё полтора часа и прикрутил FreeImage вместо ExoQuant. Результаты неоднозначные. Ниже есть картинки!

Для начала lib-файл FreeImage пришлось сконвертировать в формат Borland, так как компиляторы Borland используют формат OMF вместо MSVC’шного COFF. Утилита для этого идёт в комплекте с BCB, и не очень понятно. что мешало сделать процесс конверсии формата прозрачным для разработчика. Ну да ладно, это делается один раз и дальше можно про проблему забыть.

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

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

Из алгоритмов цветовой квантизации во FreeImage предусмотрено три, и только один из них, NeuQuant применим к моей задаче — формирование маленьких палитр. Работает он действительно в несколько раз быстрее, но тоже не упопомрачительно быстро. Но явно лучше, чем было.

Однако, качество работы NeoQuant на палитрах маленького размера очень сильно уступает ExoQuant. Вместо тысячи слов:

После отказа от nQuantCpp и libimagequant альтернатив практически не осталось.

colorcrush — квантизует цвета методом octree, у которого есть один недостаток: при малом размере палитры выбирается меньше цветов, чем запрошено. В данном случае, если задать 8 цветов (мне нужно столько), получается один сплошной цвет, то есть библиотека не выполняет свою задачу.

ImageMagick — полон необходимых возможностей, но это не библиотека, а монструозный мега-комбайн в формате утилиты для командной строки, и я не представляю, как можно её собрать из исходников во что-то подходящее. Даже в формате самостоятельной утилиты приспособить её тоже непросто ввиду специфики задачи: нужна квантизация макроблоков, значит, каждый кадр надо нарезать на полторы тысячи файликов, вызывать для них утилиту, потом комбинировать обратно. Всё это просто не сможет работать быстро.

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

Однако, есть ещё библиотека FreeImage, которая решает иной класс задач — загрузку и сохранение различных графических форматов, но также содержит квантизатор, в том числе современный на основе нейросети, и распространяется в виде dll. Из проблем — документация. Авторы почему-то решили, что наиболее подходящий формат для описания API библиотеки с сотнями функций — PDF-файл без гиперссылок внутри. И никаких альтернатив.

Тем не менее, пока что это лучший из оставшихся кандидатов, и чуть ли не последняя надежда проекта. Иначе будем кодировать видео днями напролёт.

Другое решение — использовать библиотеку libimagequant. Она менее интересна, в ней меньше алгоритмов и опций.

Как оказалось, существует куча форков этой библиотеки с непонятными родственными связями. Гугл почему-то решил выдать мне версию, где сразу предусмотрен простой C-интерфейс и сборка в dll — казалось бы, то, что надо.

Вот только собрать эту dll нужно самому, так как авторы форка не считают нужным выкладывать бинарные релизы. А написан он внезапно не на C, а на Rust, о котором я не знаю ничего, кроме названия, и узнавать никакого желания не имею — это максимально отдаляет меня от решения проблемы, а не приближает к нему.

Поискав поглубже, я смог найти форк на голом C. Всего семь файлов, датирован аж 1989, 1991 и 1997 годами — ну уж такую-то древность можно без проблем собрать прямо в BCB?

Нет, нельзя. Дефайны в заголовках, определяющие компиляторы и применяющие их специфические оптимизации, не опознают этот компилятор, stdbool.h в BCB отсутствует, а сам код имеет невиданные мной за 25 лет (а я повидал всякое) элементы типа:

return (f_pixel) {

    .a = a,

    .r = gamma_lut[px.r]*a,

    .g = gamma_lut[px.g]*a,

Чтобы собрать nQuantCpp, нужен новейший компилятор VS2022, а точнее, тулчейн v143.

Тулчейн v143 нельзя поставить в VS2017, который у меня есть. Там последний — v141.

VS2022 с искомым тулчейном v143 нельзя установить на Windows 7. У меня Windows 7.

На мой основной компьютер бесполезно ставить Windows 10+. Ему без года 10 лет и его давно пора просто менять целиком. Замена на адекватную современную конфигурацию для работы по нынешним временам обойдётся в 150-200 тысяч — неподъёмные для меня деньги (иначе давно бы обновил).

Достаточно мощного компьютера с Windows 10 у меня нет, а на те, что есть, VS2022 даже просто не влезет, не говоря про скорость работы (три слабых ноута, из которых сейчас под рукой один, самый слабый).

В результате при сборке сотни ошибок, и по-быстрому разобраться, можно ли это как-то адаптировать к моим инструментам, столь же маловероятно, как изобрести собственное решение.

И всё это потому что кому-то показалось хорошей идеей задействовать последний тулчейн ради пары готовых функций и std::filesystem, без которых все прекрасно обходились десятилетиями.

Попросить кого-то с подходящим компьютером и установленной VS2022 собрать мне библиотеку я тоже не могу, так как формат именно библиотеки, в частности, искомой dll, там не предусмотрен, и сделать это не сильно просто. А чтобы я мог это сделать, нужно, чтобы библиотека собиралась у меня.

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

Помимо median cut есть ещё с десяток алгоритмов, в том числе патентованных, с разной скоростью и качеством работы, и есть десятки научных публикаций, посвящённых вопросу — как генерировать наиболее оптимальную палитру (и каковы вообще критерии оптимальности), как быстро искать наиболее похожие цвета, и так далее. В последнее время к этому делу приспосабливают даже нейросети как наиболее оптимальное решение.

Например, вот схемка «простого» алгоритма. Он действительно проще других:

Опробовал свою новую замечательную идею усечения цветности макроблока.

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

Однако, пока что стало ещё хуже и ещё медленнее. Делаю успехи!

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

Чтобы сгенерировать табличку обхода равноудалённых пикселей, как раз подошёл масштабируемый на размер макроблока паттерн Байера. С этим я ковырялся дольше всего, пытаясь сочинить свой генератор. Также пообщался с ChatGPT, который сходу выдал мне одно рабочее решение, не обнаруживаемое никакими поисковиками. Но в итоге всё же взял вариант из статьи Bisqwit'а.

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

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

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

Из-за очень низкой скорости кодирования я не могу нормально отладить пару энкодер-декодер, устаканить форматы и алгоритмы, особенно в части оценки разности между кадрами и приоритетного кодирования макроблоков. Мне нужен отрывок хотя бы секунд в 10, а лучше в 20, чтобы понять, какой эффект дали очередные изменения, и пробное кодирование занимает 5-10 минут. А его нужно делать постоянно, десятки и потенциально сотни раз.

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

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

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

Продолжаю небольшие пополнения коллекции игр на PSP. Добавил очередной лот с Авито через доставку, три игры за 959 рублей.

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

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

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