Рубрика «Алгоритмы» - 60

image

image

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

Он был немного более размытым и это устроит не всех. Однако он был лучше своих альтернатив — на самом деле именно этот фильтр использовался в оригинальной версии Bink 2. Из-за постоянной нагрузки на работе мне никогда не удавалось вернуться к нему снова и исследовать его подробнее.

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

Предупреждение о спойлерах: правильный ответ — «вероятно, нет» и «определённо, есть». Но прежде чем мы дойдём до того, почему на этот вопрос есть два ответа и что они означают, давайте получше подготовим испытательный стенд.
Читать полностью »

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

Превосходный FAQ о квантовом превосходстве от Скотта Ааронсона - 1
Читать полностью »

Завершив создание веб-архитектуры для нашего нового веб-комикса Meow the Infinite, я решил, что самое время написать несколько давно назревших технических статей. Данная статья будет посвящена фильтру, разработанному мной несколько лет назад. Он никогда не обсуждался в области сжатия видео, хотя мне кажется, что это стоит сделать.

В 2011 году я разработал “half-pel filter”. Это особый вид фильтра, который берёт входящее изображение и максимально убедительно отображает, как бы выглядело изображение при сдвиге ровно на полпикселя.

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

При анализе поведения алгоритмов компенсации движения в традиционных halfpel-фильтрах, Джефф Робертс выяснил, что при многократном применении к последовательным кадрам они быстро деградируют, заставляя другие части видеокомпрессора ипользовать для исправления артефактов больше данных, чем необходимо. Если отключить эти исправления и взглянуть на «сырые» результаты halfpel-фильтра, то такое исходное изображение:

Как я создал фильтр, не портящий изображение даже после миллиона прогонов - 1

превращается вот в такое:

Как я создал фильтр, не портящий изображение даже после миллиона прогонов - 2

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

image

Деление — одна из самых дорогих операций в современных процессорах. За доказательством далеко ходить не нужно: Agner Fog[1] вещает, что на процессорах Intel / AMD мы легко можем получить Latency в 25-119 clock cycles, а reciprocal throughput — 25-120. В переводе на Русский — МЕДЛЕННО! Тем не менее, возможность избежать инструкции деления в вашем коде — есть. И в этой статье, я расскажу как это работает, в частности в современных компиляторах(они то, умеют так уже лет 20 как), а также, расскажу как полученное знание можно использовать для того чтобы сделать код лучше, быстрее, мощнее.
Читать полностью »

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

Синтез регулятора методом обратной задачи динамики - 1

Читать полностью »

В статье представлены четыре самых распространённых алгоритма обнаружения контуров.

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

Данные алгоритмы будут игнорировать все «дырки» в паттерне. Например, если у нас есть паттерн, подобный показанному на Рисунке 1, то обнаруженный алгоритмами контур будет похож на показанный на Рисунке 2 (синими пикселями обозначен контур). В некоторых областях применения это вполне допустимо, но в других областях, например, в распознавании символов, требуется обнаружение внутренних частей паттерна для нахождения всех пробелов, отличающих конкретный символ. (На Рисунке 3 показан «полный» контур паттерна.)

image

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

image

Читать полностью »

В ходе обсуждения достоинств и недостатков нового революционного формата с плавающей запятой Posit было cделано заявление, что вообще-то задача Posit — компактно хранить данные, а вовсе не использоваться в вычислениях; при этом сами вычисления делаются в арифметике Quire с бо́льшей точностью, которая также входит в стандарт Posit.

Ну, хранить так хранить. Что вообще значит — «хранить» числа после вычислений, выполненных с бо́льшей точностью, чем допускает формат хранения? Это значит — округлять, а округлять значит вносить погрешности. Погрешности можно оценивать разными способами — и чтобы не повторяться, сегодня мы используем спектральный анализ с помощью преобразования Фурье.Читать полностью »

Хабр, привет.

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

Метод главных компонент (PCA)/SVD

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

image

SVD — это способ вычисления упорядоченных компонентов.

Полезные ссылки:

Вводный гайд:

Читать полностью »

Кластеризуем лучше, чем «метод локтя» - 1

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

Однако процесс кластеризации по большей части относится к сфере машинного обучения без учителя, для которой характерен ряд сложностей. Здесь не существует ответов или подсказок, как оптимизировать процесс или оценить успешность обучения. Это неизведанная территория.
Читать полностью »

И ещё о сортировках

Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js