Russian Qt Forum

Задача следующая - имеется обновляющийся массив пикселей, необходимо отображать их усреднённое значение, которое, естественно, будет непрерывно во времени меняться при поступлении новых данных. Проще говоря - надо отображать не кадры, а их среднее арифметическое, т.е. 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 бита, то вообще до конца существования человеческой расы будет работать =).

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

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

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

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

Посмотрите в сторону OpenCV. Там имеется множество функций для решения подобных задач. Как пример (http://locv.ru/wiki/9.1.5.1_%D0%9D%D0%B0%D0%BA%D0%BE%D0%BF%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B8%D1%85,_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D0%B8_%D0%B2%D0%B7%D0%B0%D0%B8%D0%BC%D0%BE%D1%81%D0%B2%D1%8F%D0%B7%D0%B0%D0%BD%D0%BD%D1%8B%D1%85_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D0%B9)

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

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

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

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

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


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

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

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

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

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

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

Спасибо!

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

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

Где я ошибся в ваших формулах?:

C++ (Qt)
    float accum = 1.0;
    int count = 1;
    float An = 1.0;
    float pixelred;
    for (int k=1; k<100; k++) {
        count++;
        float newValue = 1;
 
        accum += newValue;
 
        An = ((static_cast<float>(count)-1)*An-1+newValue)/static_cast<float>(count);
 
        float temp = (pixelred * static_cast<float>(count) + newValue) / (static_cast<float>(count+1));
        pixelred = temp + 0.5;
    }
    float out = accum/static_cast<float>(count);
    qDebug() << "V1KT0P:" << out << "once_again_abc:" << An << "Igors:" << pixelred;

Выводит:
Вроде же правильно сделал...

1) Добавление 0.5 было предложено для работы с байтами (значения 0..255). Это не к месту если Вы делаете все в float и используете диапазон 1 

2) A(n) и A(n - 1) совсем не значит что нужно отнимать какую-то единицу - это значения на предыдущем (n - 1) и текущем (n) шаге.

3) если один из операндов float то второй операнд int автоматически приведется к float (старшему) и результат будет float. Поэтому сорить static_cast не нужно

1) Действительно =). Кстати погрешность накапливается поистине мизерная, через 10млн итераций всего несколько сотых процента =). Остается только измерить скорость относительно тупого метода.

3) Не могу не ставить, обычно если статиков много завожу новую переменную(все-равно компилятор оптимизирует). Если не поставлю у меня в голову постоянно лезет мысль "поставь статик" =).

огромное вам всем спасибо за участие и помощь!