И так, в классике существуют два подхода: семейство первых алгоритмов - компенсирующих движение, вторые - адаптирующиеся к движению. Первые алгоритмы реализуют либо в "железе", либо в "неторопливых" программах линейного видео монтажа. Вторые существенно менее затратны по ресурсам, а потому получили более широкое распространение. Обычно алгоритмы, адаптирующиеся к движению состоят из следующих шагов: 1. Построение карты движения 2. Фильтрация карты движения для устранения шумов 3. Интерполяция выбранного основным поля 4. Слияние основного поля и его дополняющего на основании отфильтрованной карты движения. Сами по себе операции несложны и сравнительно легко поддаются оптимизации. Однако возникают вопросы об оптимальном слиянии всех вышеперечисленных операций. По своей природе алгоритм деинтерлейсинга обрабатывает большие объемы данных. Для определености приведу объемы обрабатываемых данных на каждом этапе. Размеры буферов изображений будут приведены для стандартного разрешения 720x288 - поле, и 720x576 - кадр. Также необходимо учитывать, что стандартное цветное видео изображение требует два байта на каждый пиксель. 1. Карта движения строится по двум парам полей, порождает карту движения размерностью равной "пиксельному" размеру изображения. Таким образом, 4*(2*720*288) + (720*288) = 1866240 2. Фильтрация карты движения выполняется квадратными ядрами 3x3 пиксела размером. Это означает, что для определения значения отфильтрованного пиксела необходимо сосответствующим образом обработать значения всех его восьми соседей. Если не учитывать внутренних особенностей процесса фильтрации, то алгоритм потребляет и порождает одно поле размером 720x288. Таким образом, (720*288) + (720*288) = 414720 3. Интерполяция выбранного основным поля идет в вертикальном направлении и выполняется симметричным КИХ фильтром шестого проядка. Т.е. для определения значения выбранного пиксела необходимо обработать три пиксела непосредственно над ним и три пиксела непосредственно под ним. Таким образом, (2*720*288) + (2*720*576) = 1244160 4. Слияние полученных результатов - самая простая из операций. Требует интерполированного основного поля и его дополняющего, ну и само собой - карту движения. Таким образом, (2*720*288) + (2*720*576) + (720*288) + (2*720*576) = 2280960. Простое суммирование всех данных дает 5806080 байт. Таким образом полученная цифра абсолютно неудобоварима для современных систем, поскольку порождает огромный двунаправленный трафик память-процессор. А вот здесь и начинаются вопросы. Самым простым является слияние третьего и четвертого шагов для экономии на операциях пересылок. Тогда совмещенный третий и четвертый шаги потребуют два поля и карту движения на вход, а на выходе будут порождать всего один кадр. Казалось бы хорошо, но возникают проблемы с недостатком ресурсов процессора для выполения такой операции. Прежде всего, недостаток в индексных регистрах. Для организации интерполяции и слияния одновременно требуется порядка 11 индексных регистров - их нет, а значит в теле цикла будет значительное количество адресной арифметики и операций с указателями, эффективно блокирующей внеочередную подгрузку данных для следующих итераций цикла. Далее, для обработки потребуется порядка 9 независимых входных потоков данных и два выходных - аппаратные схемы предвыборки отдыхают, или наоборот, создают лишние проблемы. Далее, ассоциативность кэша L1 составляет всего 8, а это значит что 11 потоков данных будут постоянно вытеснять друг друга из него. Вот и вопрос, экономия на пересылке память-процессор оборачивается возможной неэффективной работой процессора по обработке данных из-за ограниченных ресурсов кэшей всех уровней. Вот и вопрос, а как же это сделать лучше? И оправдана ли экономия ресурсов FSB в обмен на пониженную эффективность работы самого процессора? У кого какие мысли по этому поводу? С уважением, v_mirgorodsky
Почему 11? Вроде 8. Две координаты на три потока входных и одного выходного. Итого 2*(3+1) и плюс два регистра у нас в запасе. Тут пробовотать надо различные способы обработки. Но поидее все данные должны уместиться в кэше. Так что число потоков недолжно повлиять. Оправдывает, так как мы еще экономим на счетчиках указателей и переходах цикла это тоже существенно. По повуду второго пункта там скорее всего фильтр можно представить как два по строчкам и столбцам и того экономимия операции 3+3 против 3*3
Пусть в регистре ecx находится растояние от начала одной строки до начала следующей, тогда [eax] указывает на строку +0, [eax+ecx] - строка +1, [eax+2*ecx] - строка +2, [eax+4*ecx] - строка +4. Для строк +3 и +5 надо изобретать дополнительный велосипед - не получается. В моем раскладе я использую [eax] - строка +0, [ebx] - строка +1, [eax+2*ecx] - строка +2, [ebx+2*ecx] - строка +3, [eax+4*ecx] - строка +4 и наконец [ebx+4*ecx] - строка +5. Это первое поле. Поскольку оба поля и выходной кадр имеют идентичные значения страйдов, то ecx может быть использован для индексирования и по второму полю. К счастью, второе поле не требует доступа к шести линиям одновременно, во втором дополняющем поле необходимо адресовать всего две строки одновременно, таким образом, [edx] и [edx+ecx] позволяют получить доступ ко всем необходимым данным. Регистр [esi] используется как указатель в карте движения, a регистр [edi] и [edi+ecx] - как указатели в буфере приемного изображения. Таким образом остались в запасе [ebp] и [esp]. Значение [ebp] я сохраняю прямо при входе в функцию, а потому его можно использовать просто как регистр общего назначения. К сожалению, использовать его в качестве индексного нельзя, поскольку не хочется закладываться на идентичность селекторов загруженных в регистры ss и ds. Таким образом индексных регистров достаточно для основного цикла с совмещенными интерполяцией и слиянием. Когда я писал 11 - это было с учетом 5 первых и 5 последних линий, обработка которых ведется несколько иным способом, а потому требует немного других значений индексных регистров. Однако с потерями, связанными с изменением указателей на переходе придется смириться. Таким образом стало более-менее понятно как скрестить 3 и 4. Похоже, что "забросить" в этот же цикл 1 с 2 уже не решается, поскольку необходимы индексные регистры еще на два поля и промежуточные вычисления результатов фильтрации. Ну и ладно, получится скрестить только 1-2 и 3-4. Тоже неплохая экономия. Здесь имеются ввиду аппаратные автоматические префетчеры, которые активируются после двух промахов на кэш-линию. Вот они и будут создавать проблемы с вытеснением в L1 кэше. По поводу два - фильтрация выполняется в два прохода. Первый фильтр выполняет эродирует полученную карту движения по очень простому правилу - если хотя бы в одном из восьми соседних пикселей не было движения, то в центральном пикселе считается что движения нет тоже. Второй фильтр противоположен первому - если хотя бы в одном пикселе в окрестности есть движение, то считается что и в центральном пикселе есть движение. Такой способ фильтрации умные дядьки в зарубежной статье называют морфологической Правда там они пользуются мудренными функциями мин() и макс() для фильтрации, но поскольку карта движения в моем случае бинарна, то операции and и or с успехом заменяют громоздкие мин() и макс(). Однако тут мы снова нарываемся на сложную ситуацию, связанную с загрузкой в векторные регистры невыровненных значений. По факту, для фильтрации надо загрузить соседей справа и соседей слева, имеющих смещение относительно текущего выровненного значения -1 и +1. Конечно существует вариант не грузить невыровненные значения, а произвести фильтрацию первой и последней точки на байтовых операциях и регистрах общего назначения. Но не понятно что же будет выгоднее по скорости. С уважением, v_mirgorodsky
v_mirgorodsky Вот тебе идея. Можно написать само модифицирующейся код. Длину строк можно вбить как константу прямо в код во время инициализации.
Хорошая идея, но к одному и тому же куску кода могут обращаться много потоков и каждый со своими параметрами и геометрическими видео изображений. Потому самомодифицирующийся код в этом конкретном случае работать не будет Да и настроить десятка три операций загрузки и выгрузки будет еще тем удовольствием
Хорошо, а что на это скажут всякого рода антивирусы? Фактически некая DLL будет создавать в сегменте кода динамически новые куски кода и передавать на них управление. Не покажется ли им это несколько подозрительным? А будет ли такой код портируемым под нечто кроме форточек? Такая идея уже как-то возникала при написании кодека. Там она была связана с большим количеством внутренних настроек для сжатия изображений, однако там остановила необходимость также корректировать смещения условных переходов. Еще вопрос, а как автоматизировать создание таблицы смещений куда надо вписывать соответствующие константы? Привязываться по листингу - как-то несерьезно, да и очень долго.
v_mirgorodsky Может, конечно я чего не понял, но если вся обработка производится только в локальных окрестностях пикселей, то здесь должна рулить блочная обработка с перекрытием. За счет блочной обработки промежуточные данные будут формироваться не целиком на все поле, а только на текущий блок ограниченного размера и соотв-но постоянно присутствовать в кэше (по кр.мере в L2). Ведь в условиях задачи не требуется формировать и сохранять карту движения или интерполированное поле целиком ? Плюс по п.2 следует уточнить алгоритм фильтрации "3х3" - можно ли тут задейстовать скользящий\циклический буфер меньшего размера и записывать итоговые значения в ту же самую карту, а не в новую. В итоге, насколько я понял, будем иметь 4 входных потока (4 вх.поля) и 1 или 2 выходных (не понял, почему 2) - в принципе "ничего страшного" с учетом блочности обработки (Правда лучше бы размерчик был-бы наоборот 288х720 и соотв-но интерполяция поля по строке, а не столбцу - поэтому в качестве запасного варианта можно иметь ввиду предварительное транспонирование полей)
leo Да, вся обработка проводится в локальных окрестностях пикселей, варианты с блочной обработкой с перекрытием активно рассматриваются, однако как раз они приводят к очень активной работе с указателями внутри цикла обработки. Строим карту движения - один набор индексных регистров, фильтруем карту движения - другой, и так дальше. В тоже время и Фог и сам Интел в своих мануалах категорически предостерегает от модификации индексных регистров внутри цикла, мотивируя это тем, что такие модификации сбивают с ритма аппаратные модули предвыборки, приводя к существенному замедлению процесса обработки данных. Вот и вопрос - на сколько существенно? В принципе, почти вся математика деинтерлейсера уже готова, можно будет просто попробовать и выбрать более быстрый вариант. По фильтрации карты движения - два противоположных фильтра. Поскольку в моем случае интересует просто факт наличия движения, то его логично кодировать как 0xFF, а отсутствие движения - как 0x00. Тогда первый фильтр работает как and по окрестности 3x3. Первый фильтр таким образом удаляет шумы и несколько "разъедает" края больших областей движения. Далее, результат работы первого фильтра передается на вход второму - он работает как or по такой же окрестности 3x3. Таким образом, только область движения как минимум размером 3x3 проходит фильтрацию неизменной, остальные области движения считаются шумами и удаляются. Такой способ фильтрации называется морфологическим. В тестовой реализации на C++ дает просто замечательные результаты. Поскольку карта движения занимает один байт на каждый пиксель, то в обоих фильтрах происходит невыровнянная загрузка значений в векторные регистры. Чего-нибудь типа: Код (Text): movq mm0,[ebx - 1] movq mm1,[ebx] movq mm2,[ebx + 1] movq mm3,[ebx + ecx - 1] movq mm4,[ebx + ecx] movq mm5,[ebx + ecx + 1] pand mm0,mm3 pand mm1,mm4 pand mm2,mm5 movq mm3,[ebx + 2 * ecx - 1] movq mm4,[ebx + 2 * ecx] movq mm5,[ebx + 2 * ecx + 1] pand mm0,mm3 pand mm1,mm4 pand mm2,mm5 pand mm0,mm1 pand mm0,mm2 Если при входе в код ebx указывал на средину (!) нулевой строки карты движения, то результат фильтрации относится к первой строке карты движения, расположенной по тому же смещению [ebx + ecx]. Так работет первый фильтр, второй имеет аналогичную функциональность, с той лишь разницей, что операции pand заменяются на por. Из того, что я вижу, результаты фильтрации можно попробовать сохранить в ту же карту движения, однако обработка должна вестись блоками состоящими как минимум из 3 строк. Если поля предварительно транспонировать, то можно будет использовать команды типа векторного умножения с совмещенным сложением - pmaddwd. В этом основной смысл, или я что-то путаю? Мне кажется, что затраты на транспонирование не окупятся, хотя я могу ошибаться. Такое впечатление, что надо сделать и лишь потом можно будет оценить производительность.
v_mirgorodsky Если использовать технику блок-префетча, то ничего этого не будет. Т.е. сначала в ускоренном режиме (с шагом в 64 байта) префетчим n-строк из 4-х полей в L2 (где n >= 6 для интерполяции поля). Затем обабатываем эти строки блоками (n x m), где m выбирается из условия, чтобы все необходимые данные умещались в L1 - тогда "активная работа с индексами" никак не повлияет на аппаратный префетч. Поскольку обработка n-строк по всей видимости получится "не хилой", то "искусно" добавив в нее префетчи новых порций строк для последующей обработки, можно будет существенно "скрыть" время подгрузки новых порций данных из ОЗУ. Кстати, в связи с этим немаловажный вопрос - обрабатываются ли поля независимыми четверками или же с перекрытием (1-4, затем 5-8, 9-12 или же 3-6,5-8) ?
leo Общую идею уловил - буду пытаться активно использовать принудительную подчитку данных наперед, локальных циклов получается много, особых проблем с "встраиванием" префетчей быть не должно. Обработка действительно получается "нехилой" - только код вертикального интерполятора занимает порядка 100 команд Еще сильно добавляют головной боли "краевые" условия - начала и концы строк приходится обрабатывать специально. К сожалению ничего не смог придумать относительно "невыровненной" загрузки данных карты движения. По тестам получается, что скорость таки падает, но "дофильтровывание" первого и последнего пикселя в блоке из 8 или 16 пикселей на регистрах общего назначения получается все равно слишком медленным. Надо будет еще подумать над вставлением "невыровненных" пикселей из значений регистров с предыдущего и следующего шагов. Поля обрабатываются в варианте 1-4, 3-6, 5-8, но следующая пара становится доступной только через 40ms, что по меркам почти любого CPU - вечность Потому оптимизировать собственно вопрос перекрытия вероятнее всего излишне. Можно, конечно, сбуферизировать несколько пар полей, потом запустить обработку в пакете, однако затраты на объемы памяти растут просто в геометрической прогрессии. А работать этот алгоритм собирается в минимуме на системах с восемью независимыми каналами. Очень многие мои задачи решались бы проще и эффективнее, если бы можно было себе позволить такую роскошь, как глубокая буферизация данных
