Использование SIMD инструкций как бы подразумевает, что будут не только, например, выполняться сложение для всех элементов вектора с помощью одной операции, но также векторная загрузка исходных данных и векторное сохранение результатов. Опять же, так как, векторная загрузка/сохранение оптимально работает для выровненных данных, то хороший алгоритм должен по возможности использовать эту возможность.
Вы не совсем правы. Есть такая операция в SSE2 — _mm_sad_epu8 (в AVX2 — _mm256_sad_epu8), которая позволяет за одну операцию найти сумму абсолютных разностей 1-байтных беззнаковых целых чисел (упоминается в статье). Иначе говоря:
__m128i a, b, c;
с = _mm_sad_epu8(a, b); эквивалетна:
unsigned long long c[2];
unsigned char a[16], b[16];
Т.е. одна эта операция SSE2 позволяет заменить 62 операции для скалярного кода (для AVX2 — 124 операции соответственно). Отсюда и возможен потенциальный выигрыш до ста раз. Хотя конечно на большинстве других операций он гораздо скромнее — порядка 10 раз для SSE2 кода и 15 раз для AVX2 кода.
Данные взяты из проекта Simd.
Как уже было отмечено выше, тестирование каждого модуля по отдельности — это далеко не тоже самое, что протестировать все модули в связке. В сложных проектах между отдельными модулями иногда бывают не тривиальные связи — например, ошибка возникает в модуле 3, при специфических параметров в модулях 2 и 7. Потому для полной гарантии наверное действительно надо совершить полный перебор все возможных комбинаций параметров для всех модулей. Иначе говоря точное решение имеет экспоненциальную сложность. Пара десятков параметров, каждый из которых может принимать несколько значений и задача полного перебора фактически становиться нерешаемой.
Здесь можно сделать шаг назад, и спросить: а нужна ли нам 100% уверенность? Может достаточно 99% или там 99.9%. В последнем случае достаточно покрыть полными тестами основные сценарии использования. А для проверки случаев экзотических нетривиальных связей между модулями — использовать тесты со случайными (но естественно в разрешенных границах) наборами параметров. Если параметры выбираются действительно случайным образом в каждом тестовом случае, то достоверность такого тестирования растет как квадратный корень от общего числа испытаний. Получаем своеобразное тестирование по методу Монте-Карло. :)
Градиентный спуск с переменным шагом надо делать над исходным изображением, а не над уменьшенным (правда это частично компенсируется необходимостью строить многомасштабные изображения). У многомасштабного изображения есть другой плюс — в процессе их построения происходит усреднение и сглаживание, что уменьшает вероятность попасть в ложный локальный максимум.
Ну так, а у меня и 1.5 миллисекунды, из которых поиск корреляционного максимума — 0.3 миллисекунды, а остальное компенсация ARGB изображения методом билинейной интерполяции.
Зависит от максимально возможного смещения, которое компенсируется (выступает в качестве параметра алгоритма). Для максимально возможного значения сравнивается действительно где-то половина изображения, но по умолчанию процентов 75.
В качестве корреляционной функции использовалась сумма абсолютных разностей точек изображений. Максимальное смещение — где-то четверть от высоты изображения.
Добавил пример с сопровождением объектов. Не понимаю, почему вы мне не верите — алгоритм реализован уже пять лет назад. И 4 года как минимум присутствует в готовых продуктах.
Работает честно — во время тряски движущиеся объекты сопровождаются детектором движения. В данном примере тоже все честно — я сам лично штатив с камерой тряс :).
Наверное мы не совсем точно описали. Но детектирование происходит не только на входе и выходе, а на всем протяжении зоны. В частности на рисунках 3 и 4 видны эти промежуточные области в виде синих квадратиков. Входи и выход задаются оператором при калибровке, а остальные зоны размечаются автоматически.
Алгоритм определяет движущийся объект и проводит его классификацию (человек или машина) — в данном случае это два идущих рядом человека. 1 — это не количество, а номер объекта.
Свое время писал стабилизатор правда для стационарных камер. Нахождения смещения основывалось на простой корреляции методом последовательного приближения на разных масштабах. После нахождения смещения, его значение уточнялось с субпиксельной точностью. Оптимизировал нахождение корреляции и выполнение смещения под SSE2. Общее время работы алгоритма было менее 1 мс для мегапиксельного изображения.
Реализовывал медианный фильтр по алгоритму из последней вашей ссылки. Да он позволяет обрабатывать изображения с одинаковой скоростью не зависимо от размера окна. Но эта постоянная скорость все же очень низкая (около секунды для HD разрешения, на сколько я помню). В области где я работаю (видеоаналитика), такая скорость неприемлема. Да и не требуются для нас медианные фильтры большого радиуса. максимум 5x5.
Спасибо за такой развернутый комментарий. Честно говоря, я не знал что уже GCC дорос до автовекторизации подобных выражений. Буду экспереметировать и курить доки.
Тем не менее, пример, который я привел — скорее исключение, чем правило. Обычно в алгоритме обработки изображения присутствует необходимость паковки и распаковки векторов, обработка краевых значений, маскирования и другие преобразования, которые не очень способствуют автовекторизации. Будет ли она работать в таком случае?
__m128i a, b, c;
с = _mm_sad_epu8(a, b); эквивалетна:
unsigned long long c[2];
unsigned char a[16], b[16];
c[0] =
a[0] > b[0]? a[0] — b[0]: b[0] — a[0] +
a[1] > b[1]? a[1] — b[1]: b[1] — a[1] +
a[2] > b[2]? a[2] — b[2]: b[2] — a[2] +
a[3] > b[3]? a[3] — b[3]: b[3] — a[3] +
a[4] > b[4]? a[4] — b[4]: b[4] — a[4] +
a[5] > b[5]? a[5] — b[5]: b[5] — a[5] +
a[6] > b[6]? a[6] — b[6]: b[6] — a[6] +
a[7] > b[7]? a[7] — b[7]: b[7] — a[7];
c[1] =
a[8] > b[8]? a[8] — b[8]: b[8] — a[8] +
a[9] > b[9]? a[9] — b[9]: b[9] — a[9] +
a[10] > b[10]? a[10] — b[10]: b[10] — a[10] +
a[11] > b[11]? a[11] — b[11]: b[11] — a[11] +
a[12] > b[12]? a[12] — b[12]: b[12] — a[12] +
a[13] > b[13]? a[13] — b[13]: b[13] — a[13] +
a[14] > b[14]? a[14] — b[14]: b[14] — a[14] +
a[15] > b[15]? a[15] — b[15]: b[15] — a[15];
Т.е. одна эта операция SSE2 позволяет заменить 62 операции для скалярного кода (для AVX2 — 124 операции соответственно). Отсюда и возможен потенциальный выигрыш до ста раз. Хотя конечно на большинстве других операций он гораздо скромнее — порядка 10 раз для SSE2 кода и 15 раз для AVX2 кода.
Данные взяты из проекта Simd.
Здесь можно сделать шаг назад, и спросить: а нужна ли нам 100% уверенность? Может достаточно 99% или там 99.9%. В последнем случае достаточно покрыть полными тестами основные сценарии использования. А для проверки случаев экзотических нетривиальных связей между модулями — использовать тесты со случайными (но естественно в разрешенных границах) наборами параметров. Если параметры выбираются действительно случайным образом в каждом тестовом случае, то достоверность такого тестирования растет как квадратный корень от общего числа испытаний. Получаем своеобразное тестирование по методу Монте-Карло. :)
synesis.ru/products/ip-videoserver-kipod-server?searched=KIPOD&advsearch=oneword&highlight=ajaxSearch_highlight+ajaxSearch_highlight1
Тем не менее, пример, который я привел — скорее исключение, чем правило. Обычно в алгоритме обработки изображения присутствует необходимость паковки и распаковки векторов, обработка краевых значений, маскирования и другие преобразования, которые не очень способствуют автовекторизации. Будет ли она работать в таком случае?