Отрисовка усреднённых значений

[once_again_abc]

Задача следующая - имеется обновляющийся массив пикселей, необходимо отображать их усреднённое значение, которое, естественно, будет непрерывно во времени меняться при поступлении новых данных. Проще говоря - надо отображать не кадры, а их среднее арифметическое, т.е. 1й кадр отрисовали - ОК, пришел 2й кадр - сложили пиксели 2го с соответствующими пикселями 1го кадра и поделили на ноль два - нарисовали получившееся среднее арифметическое, пришел 3й кадр - сложили пиксели 3го кадра с соответствующими пикселями 1го и 2го кадров и поделили на три - нарисовали получившееся среднее арифметическое и т.д. до бесконечности переполнения сумматоров или делителей (что раньше переполнится); при переполненни каким-то хреном еще переносим результаты счетчиков и пошли считать заново...

Естественно хочется быстро и с малой кровью памятью сделать.

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

Спасибо!

ПС. либо нужен быстрый алгоритм получения A[n] из A[n-1], где A - арифметическое среднее для текущего значения пикселя.

[V1KT0P]

Задача следующая - имеется обновляющийся массив пикселей, необходимо отображать их усреднённое значение, которое, естественно, будет непрерывно во времени меняться при поступлении новых данных. Проще говоря - надо отображать не кадры, а их среднее арифметическое, т.е. 1й кадр отрисовали - ОК, пришел 2й кадр - сложили пиксели 2го с соответствующими пикселями 1го кадра и поделили на ноль два - нарисовали получившееся среднее арифметическое, пришел 3й кадр - сложили пиксели 3го кадра с соответствующими пикселями 1го и 2го кадров и поделили на три - нарисовали получившееся среднее арифметическое и т.д. до бесконечности переполнения сумматоров или делителей (что раньше переполнится); при переполненни каким-то хреном еще переносим результаты счетчиков и пошли считать заново...

Естественно хочется быстро и с малой кровью памятью сделать.

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

Спасибо!

ПС. либо нужен быстрый алгоритм получения A[n] из A[n-1], где A - арифметическое среднее для текущего значения пикселя.

Давай возьмем для примера банальный случай когда для каждого канала пикселя используется 32 бита. В результате если все время будет приходить 255, то пиксели наши переполнится через 16843009 циклов. Теперь допустим ты снимаешь со скоростью 60 кадров в секунду, тогда переполнение будет через 280716 секунд или 4678 минут или 78 часов. В итоге чтобы небыло переполнения достаточно раз в 39 часов делить все на 2. Конечно это приведет к погрешности, но эта погрешность будет настолько мала что ею можно пренебречь.
А если возьмешь 64 бита, то вообще до конца существования человеческой расы будет работать =).

[Igors]

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

Это случай интересный, но совсем не банальный - float на канал, такие имеджи называются HDRI. Вероятно имелось ввиду 8 бит на канал, 32-битный имедж

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

Если число осреднений одно и то же для всех пикселей - то зачем хранить его для каждого? Просто взвешиваетесь, напр

Код

C++ (Qt)
float temp = ((float) pixel.red * num_frames + new_pixel.red) / (num_frames + 1);
pixel.red = int (temp + 0.5f);
 

Т.е. просто храните текущее значение и вес - один для всех. Здесь будет потеря точности если 1 байт на канал. Если это крытычно - храните float на канал

[alexis031182]

Посмотрите в сторону OpenCV. Там имеется множество функций для решения подобных задач. Как пример

[V1KT0P]

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

Это случай интересный, но совсем не банальный - float на канал, такие имеджи называются HDRI. Вероятно имелось ввиду 8 бит на канал, 32-битный имедж

Я так понял приходит 8 бит на канал, надо усреднять их. Берем и тупо делаем копию 8 битных каналов размерностью 64 бита.
И заводим счетчик. Как только поступает новая порция данных, то добавляем значения в 64 битные каналы. Затем эти 64 битные каналы делим на счетчик и сохраняем в 8 битные каналы. Все просто до предела и никаких переполнений. Где-же здесь интересный случай?

[Igors]

Я так понял приходит 8 бит на канал, надо усреднять их. Берем и тупо делаем копию 8 битных каналов размерностью 64 бита.
И заводим счетчик. Как только поступает новая порция данных, то добавляем значения в 64 битные каналы. Затем эти 64 битные каналы делим на счетчик и сохраняем в 8 битные каналы. Все просто до предела и никаких переполнений.

Зачем 64 если можно обойтись 32 (float)? А если точность не очень важна то и одним обычным 8-битным имеджем 

Где-же здесь интересный случай?

Не "здесь" а "там". Есть имеджи 32 бита на канал, как Вы писали. Канал может иметь значения > 1, напр red = 5.2. А зачем это нужно если монитор все равно отображает от 0 до 1 что соответствует байту 0..255 (true color)?

[V1KT0P]

Не "здесь" а "там". Есть имеджи 32 бита на канал, как Вы писали. Канал может иметь значения > 1, напр red = 5.2. А зачем это нужно если монитор все равно отображает от 0 до 1 что соответствует байту 0..255 (true color)?

Ну так 5.2 может получиться только на 6 цикле, что в итоге преобразуется в 5.2/6=0.8666 как раз монитор отобразит байт 221.

[once_again_abc]

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

Это случай интересный, но совсем не банальный - float на канал, такие имеджи называются HDRI. Вероятно имелось ввиду 8 бит на канал, 32-битный имедж

да, речь идет о числах float.

Если число осреднений одно и то же для всех пикселей - то зачем хранить его для каждого? Просто взвешиваетесь, напр

Код

C++ (Qt)
float temp = ((float) pixel.red * num_frames + new_pixel.red) / (num_frames + 1);
pixel.red = int (temp + 0.5f);
 

Т.е. просто храните текущее значение и вес - один для всех. Здесь будет потеря точности если 1 байт на канал. Если это крытычно - храните float на канал

num_frames - это число усреднений? правильно я вас понял?
т.е. массив float pixel + одно значение num_frames и текущая картинка расчитывается по этим + массив соответствующих float new_pixel?

[V1KT0P]

да, речь идет о числах float.

Без разницы алгоритм тот-же.
accum += newValue;
count++;
out = accum/count;
Все кроме count - float.

[once_again_abc]

да, речь идет о числах float.

Все кроме count - float.

прошу прощения, выделенное не понял 

[Igors]

num_frames - это число усреднений? правильно я вас понял?
т.е. массив float pixel + одно значение num_frames и текущая картинка расчитывается по этим + массив соответствующих float new_pixel?

Ну да. В принципе потеря точности на 8-битном не так уж страшна при бухгалтерском округлении, а памяти в 5 раз меньше. Можно хранить в RGBE (8-битовые float значения). Возможно стоить плясать от того как Вы собираетесь хранить данные на диске, тогда будет ясно какая точность нужна.

[V1KT0P]

прошу прощения, выделенное не понял 

float accum;
float newValue;
int count;
float out;

[once_again_abc]

num_frames - это число усреднений? правильно я вас понял?
т.е. массив float pixel + одно значение num_frames и текущая картинка расчитывается по этим + массив соответствующих float new_pixel?

Ну да. В принципе потеря точности на 8-битном не так уж страшна при бухгалтерском округлении, а памяти в 5 раз меньше. Можно хранить в RGBE (8-битовые float значения). Возможно стоить плясать от того как Вы собираетесь хранить данные на диске, тогда будет ясно какая точность нужна.

Я тут додумался до вычисления текущего СА (ср. арифметич) из предыдущего: An = [(n-1)*An-1 + an] / n
Кстати, здесь я так же могу хранить одно значение n - усреднений для всех пикселей и массив предыдущих СА. И мне кажется эта шутка чуть чуть быстрее чем весовая формула...

[once_again_abc]

прошу прощения, выделенное не понял 

float accum;
float newValue;
int count;
float out;

Спасибо!

[Igors]

Я тут додумался до вычисления текущего СА (ср. арифметич) из предыдущего: An = [(n-1)*An-1 + an] / n
Кстати, здесь я так же могу хранить одно значение n - усреднений для всех пикселей и массив предыдущих СА. И мне кажется эта шутка чуть чуть быстрее чем весовая формула...

Это та же самая весовая формула. А если нужна скорость, то можно распараллелить (здесь без проблем) или (здесь еще лучше) задействовать SSE

Если Вы планируете осредненные значения больше 1.0 то надо подумать как их отображать