Замените операторы ветвления операциями сдвига битов

Question

Я пишу алгоритм бинаризации изображения, который просто преобразует значение яркости каждого пикселя (изображение в градациях серого) в черный или белый. В настоящее время алгоритм бинаризации каждого пикселя примерно такой:

if( grayscale[x] < thresholdValue)
{
bitonal[x] = 1;
}

(на самом деле это упрощение АКТУАЛЬНОГО алгоритма, потому что битональное изображение на самом деле является битовым изображением (каждый индекс массива содержит 8 пикселей), поэтому я фактически упаковываю 1 в текущем индексе массива ... но я не думаю это меняет мой вопрос.

То, что я пытаюсь сделать, это устранить необходимость в операторе if.

Я думал о том, чтобы сделать что-то подобное. Вычтите значениеvalValue по шкале серого, а затем выполните некоторую хитрость манипулирования битами, чтобы очистить или сдвинуть биты так, чтобы в случае результата (grayscale[x]-threshold) is less than 0, I get a 0. otherwise I would get a 1. Если проще сделать это наоборот (if grayscale[x]-threshold < 0 + bitwise trickery get a 1, else get a 0), это также сработало бы ... пока я могу избавиться от операторов ветвления ... любая помощь приветствуется ..

Answer 1

bitonal[x] = (grayscale[x] < thresholdValue);

Answer 2

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

bit = (a<b);

все еще генерирует инструкцию перехода на моей платформе (TI F2812). Кажется, у компилятора нет прямого способа переместить флаг состояния из сравнения в регистр, поэтому вместо этого он генерирует что-то вроде

 temp_register =  0
 cmp a,b
 branch to label if LT
 temp_register = 1
label:
 bit = temp_register

Однако процессор имеет встроенные операторы max и min. Поскольку ветвление довольно дорогое, этот код на самом деле работает быстрее:

bit = min(max((b-a),0),1);

Результат max будет ненулевым, только если a min преобразует любое ненулевое значение в 1.

Это сильно зависит от процессора и может вообще не применяться на X86.

Answer 3

Если яркость является 8-битным значением, то вы можете иметь массив из 256 элементов, которые содержат либо 0, либо 1 (первые threshold элементы массива содержат 1, а остальные элементы содержат 0.

bitonal[x] = array[grayscale[x]];

Answer 4

Возможно:

bitonal[x] = ((grayscale[x] - thresholdValue) >> 31) xor 1;

Предполагается, что ваш язык не приравнивает логические и целочисленные значения (как в C и C ++).

Answer 5

На каком языке вы работаете? Есть ли в языке функции min / max? (C ++ и Java, например, оба делают) Если язык делает, это был бы один из способов устранить if ... например Min (grayscale [x]