Потоковая фильтрация изображений (Pipe Line Filtering)

Потоковая фильтрация изображений (Pipe Line Filtering)

Суть проблемы и основания для разработки системы потоковой фильтрации

Краткий обзор архитектуры системы

Полосовой буфер

Предварительная обработка графа, топологическая сортировка

Балансирование задержек

 

 


Суть проблемы и основания для разработки системы потоковой фильтрации

Довольно широкий класс фильтров изображений работает по следующей схеме:

На входе фильтра – N ≥ 1 изображений, возможно разного размера и типа, на выходе  M ≥ 1 изображений, тоже возможно различных размеров и типов. Для построения значения выходного изображения m в пикселе с координатами (x,y) требуется значения пикселей на входных изображениях (части или на всех) в точке с координатами (x’,y’) и ее некоторой окрестности. Координаты (x’,y’) вычисляются для каждого используемого входного изображения как функция от (x,y), причем наиболее распространенный и важный случай – линейная зависимость:

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

Приведем примеры:

В указанную схему укладываются:

ü      преобразование пиксель в пиксель, например гистограммные преобразования, гамма коррекция, эквализация, получение негатива;

ü      линейные фильтрации, осуществляемые как свертка с некоторой функцией имеющей компактный носитель: гауссово сглаживание (blur), среднее по окрестности, sharpening, emboss;

ü      нелинейные фильтры, такие как операторы Робертса, Собеля, Превитта, Канни, DiZenzo, Himage, RImage, статистическое дифференцирование;

ü      медианная фильтрация и все ранговые алгоритмы, включая скользящую эквализацию и Bilateral filtering;

ü      вычисление многих текстурных признаков, например по матрице смежности, Лоэва и др.

ü      масштабирование изображения (zoom, resize) алгоритмами ближайшего соседа, билинейной, смещенной билинейной, бикубической интерполяциями, интерполяция B-сплайнами и др.

ü      построение пирамиды детальности (гауссовой пирамиды, Scale Space);

и многие другие.

В указанную схему НЕ укладываются:

ü      интегральные преобразования изображений (Фурье, Хартли, Хафа);

ü      вейвлет преобразование;

ü      поворот изображения (если угол поворота φ значителен, так, что width* sin(φ) ≥ 10-60;

ü      резиновые искажения (тоже в случае если они значительны), такие как например Wave, Ripple, преобразование спутниковых изображений в географическую проекцию.

 

Рассмотренная ситуация на первый взгляд кажется тривиальной, однако при практической реализации подобных фильтраций возникают ряд существенных проблем. Основная из них – то, что такая одиночная фильтрация как правило не представляет интереса, а интерес представляет последовательность фильтраций, образующая некоторый маршрут. Например, упомянутый выше детектор краев Канни на самом деле представляет собой такую цепочку из элементарных фильтраций (эффективная вычислительная реализация основывается на сепарабельности функции Гаусса):

Таким образом получается достаточно сложная схема. Прямолинейная реализация состоит в построении промежуточных изображений (показаны желтым цветом). Более того, несмотря на то, что исходное изображение обычно 8-битное, промежуточные изображения целесообразно строить как изображения с пикселями в виде чисел с плавающей точкой, как минимум 32-битного float. Таким образом, кроме исходного и результирующего изображений одинакового размера, в памяти необходимо дополнительно держать 6 изображений в 4 раза большего размера! С помощью техники повторного использования, количество таких массивов памяти можно снизить с 6 до 4-5, но не меньше (учитывая, что изображение «направлений» градиента удобнее хранить по компонентам). Таким образом видно, что даже достаточно простая схема фильтрации в разработке достаточно сложна и требует большого количества ресурсов, а их экономия усложняет схему и делает каждую такую разработку уникальной, мало пригодной для повторного использования фрагментов кода в других задачах. Следует еще упомянуть, что при вычислении сверток возникает альтернатива либо не обрабатывать изображения в районе его краев, что по мере последовательных фильтраций ведет к неуклонному уменьшению обработанной части изображения , либо как то дополнять изображения за пределами краев, в данном случае на половину размера носителя Гауссовой функции (обычно она полагается нулем за пределами 2 сигма). Это ведет к созданию еще одной копии исходного изображения и некоторому увеличению размера промежуточных изображений, дополнение обычно осуществляется методом зеркального отражения изображения относительно краев.

 

Однако в описанной выше схеме нет никакой необходимости держать в памяти промежуточные изображения целиком. В момент вычисления некоторой строки выходного изображения достаточно держать в памяти только несколько строк промежуточных изображений (окрестность) около того же номера строки, а для вычисления соответствующих строк этих изображений – в свою очередь требуется иметь в памяти только некоторую полосу исходных для них изображений и т.д. Установив, что обработка всех изображений осуществляется сверху вниз строка за строкой приходим к тому, что промежуточные изображения могут быть виртуальными и представляться в памяти в виде скользящего полосового буфера. В результате выполнения каждого отдельного элементарного фильтра полосовой буфер на его выходе сдвигается на одну строку и дополняется вычисленными величинами одной новой строки, в свою очередь после этого буферы на входе этого фильтра также могут быть обновлены на следующую строку.

 

В качестве примера был рассмотрен детектор границ Канни, однако есть много других алгоритмов, сложность которых несопоставимо выше, но укладывается в указанную схему. В качестве примера можно упомянуть алгоритм совмещения изображений (Image Registration) [@Dufour], частью которого является обнаружение и сопоставление (correspondence problem) характеристических точек в пространстве переменного разрешения (Scale Space) путем построения и сравнения вектора признаков из дифференциальных инвариантов для каждой обнаруженной точки. Заметим, что под переменной размерностью в данном случае понимается построение набора изображений отличающихся масштабом, охватывающих диапазон масштабов около 6 раз с шагом в 1.1-1.2 раза, т.е около 25-40 изображений по каждому из которых надо вычислять свертки с различными производными функции Гаусса.

 


Краткий обзор архитектуры системы

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

 

Архитектура системы выбрана следующая:

ü      Основой системы является полосовой буфер (StripBuffer).

ü      Все фильтры порождаются от общего базового класса FilterBase.

ü      Каждый фильтр имеет входы и выходы, которые представляются классами InPort и OutPort.

ü      Выход может быть подключен к любому количеству входов, а вход может быть подключен только к одному выходу.

ü      Полосовой буфер является членом класса OutPort

ü      Входами системы (поставщиками данных-изображений) являются фильтры у которых 0 входов и ≥1 выходов.

ü      Приемниками данных являются фильтры у которых 0 выходов и ≥1 входов.

 


Полосовой буфер

Основой системы Потоковой фильтрации (Pipe Line Filtering) является полосовой буфер (StripBuffer). Выходом каждого выходного порта фильтра OutPort является по определению одна строка нового изображения. Однако, чтобы ее вычислить для ряда обработок надо знать некоторую окрестность для каждого пикселя соответствующей входной строки.

Будем считать, что для вычисления значения пикселя в точке с координатами (x,y) на выходном изображении требуется знание данных в окрестности точки с координатами (x’,y’) на входном изображении фильтра; размер окрестности задается структурой:

  
    struct Extent
    {
        int  left;
        int  right;
        int  before;
        int  forward;
    };
  

Поэтому помимо строки с таким же номером входного изображения (виртуального) в буфере должны быть

ü      before строк до нее

ü      forward строк после нее.

Здесь сразу возникает проблема, что при на краях изображения окрестность будет выходить за фактические пределы изображения. Поэтому требуется дополнять изображение за краями на before строк вверх, на forward строк вниз, на left столбцов влево и на right столбцов вправо.

 

Таким  образом размер буфера должен быть

 

Схематически буфер представлен на рис. @BufPic . Белым цветом показано виртуальное изображение, представляемое буфером, в зелено-голубой гамме – текущее положение буфера на этом виртуальном изображении. Только те данные, которые в данный момент попадают в буфер реально существуют в памяти компьютера, предыдущие строки виртуального изображения уже забыты, а последующие – еще неизвестны. Цветом на рисунке также показано дополнение виртуального изображения и буфера на величины,  задаваемые структурой Extent.

В предлагаемой системе дополнение изображения осуществляется отражением содержимого изображения относительно первой и последней строк и крайнего левого и крайне правого столбца на количество строк/столбцов, задаваемых структурой Extent . Дополнение влево и вправо выполняется тривиально, так как строка данных оказывается целиком в буфере и задача – скопировать соответствующее число пикселей. Единственным разумным ограничением представляется потребовать

,

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

Рис. @BufPic . Виртуальное изображение и полосовой буфер.

 

Дополнение вверх и вниз – не тривиально, так как строки поступают в буфер по одной. Если , то получив одну строку буфер готов к обработке следующим фильтром, однако если это не так, то следующий фильтр сможет работать только после того, как буфер получит  строк, где

Таким образом можно говорить, что буфер создает задержку в потоке данных в системе фильтрации.

Полагается, что данные лежат в буфере как и в изображении (его полосе высотой ) в одномерном массиве пиксел за пикселом, строка за строкой.

Примем нумерацию строк в буфере относительно центральной строки (соответствующей как если бы ).

При переходе к следующей строке – содержимое имеющееся в буфере сдвигается на 1 строку вверх с помощью memmove() и новая строка записывается в конец, в строку с номером forward относительно центра.

Однако в начале работы ситуация другая.

Первая поступившая строка укладывается в центральную строку буфера, Вторая поступившая строка укладывается в строки буфера с номерами y=1 и y=-1 относительно центра, и т.д. до тех пор, пока номер строки не достигнет . Далее до достижения номера строки  поступившая строка должна укладываться в строку +/-y в зависимости от того, что больше, before или  forward. Существенным является следующее обстоятельство: если , то после закладки в буфер before+1 строк, буфер готов к выдаче данных и это происходит с задержкой  delay=before. Однако следующие beforeforward  строк буфер уже  содержит в себе и может выдать без закладки в него дополнительных данных путем внутренней переорганизации: сдвиг вверх на 1 строку с помещением уходящей строки в конец. Задержка выдаче данных при этом уменьшается каждый раз на единицу. Это создаст серьезные проблемы при балансировке  системы фильтров (см. ниже), поэтому размер буфера всегда подстраивается следующим образом:

Затем, как описывалось ранее – идет обработка центральных строк изображения, т.е. сдвиг в массиве и дописывание очередной строки в конец.

Когда достигаются последние строки изображения – ситуация меняется. Новых данных уже поступить не может, и для отражения вниз надо использовать то, что уже есть в буфере. Если  то проблем нет. Сдвигая буфер на строку вверх скопировать одну строку из буфера вниз в качестве «нового поступления». Точнее в строку с номером forward относительно центра надо положить строку с номером (новым, после сдвижки) forward-2k (k=1,2,…), k – номер шага. Такая операция должна быть проделана forward раз и последняя вкладываемая строка должны браться со смещения forward-2*forward=-forward. Для работоспособности указанной схемы требуется, чтобы эта строка существовала в буфере, т.е.

before>=forward.

Так как в большинстве практически интересных фильтров окрестность симметрична, или ассиметрична не более чем на 1, можно было бы идти на возможные накладные расходы и поддерживать буфер из 2*max(before,forward)+1 строк.

Но может потребоваться также буфер задержки для обеспечения работы фильтров с несколькими входами, по которым задержка различна и самый простой способ – нагрузить этот буфер такой функциональностью.

В этом случае – памяти все равно потребуется 2*max(before,forward)+1 строк.

Однако сдвижку на 1 строку всего этого буфера потребуется выполнять только для нескольких последних поступивших строк, а для остальных выполнять сдвижку с помощью mommove() только before+forward строк на 1 строку.

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

Еще одной особенностью полосового буфера является возможность его множественного использования, несколько фильтров может читать данные из одного и того же буфера. Действительно, если несколько фильтров подключены к выходу одного буфера, и все они требуют для работы разные окрестности (Extent), то достаточно установить размер расширения буфера равным максимальным по каждой компоненте Extent величинам.  При этом все условия будут соблюдены. Однако проявляется дополнительный эффект: задержка теперь для разных входов может быть различной и одновременно любой величиной из некоторого диапазона:

Такой буфер можно назвать резиновым.

 

 

 

 

 

 

Предварительная обработка графа, топологическая сортировка

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

Предлагается следующее решение:

Системе предъявляются только фильтры источники и приемники;

Система от ситочников к приемникам прослеживает по графу построенной системы задействованные фильтры и формирует внутри себя их массив, что является принятым представлением графа, когда вершины пронумерованы и однозначно за O(1) операций находятся по номеру. В ходе поиска задействованных вершин проверяется, что все приемники достигнуты, иначе происходит генерация исключительной ситуации, с сообщением какая именно вершина не была достигнута, что помогает в поиске ошибок. В этом же процессе выполняется топологическая сортировка графа системы. И поиск петель и циклов, которые по определению системы запрещены.  Результат может быть выведен в формате .dot системы GraphViz, что позволяет визуально представить построенную систему. Особенностью является построение работы так, что вывод отладочного файла *.dot  происходит до генерации исключения, что особенно важно при отладке. Если все прошло успешно выполняется обратный поиск от приемников к источникам, в ходе которого проверяется, что нет узлов (фильтров) которые не были ранее включены в граф (обычно – это ошибка, что указаны не все источники). В ходе этих проверок не могут быть выявлены только ошибки, связанные с тем, что

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

- При связывании фильтров между собой, часть связей (ссылок) невалидна, например, система была построена из нескольких фильтров, после один из фильтров  - объект C++ удален операцией delete, а после этого источники и приемники были переданы системе. Но такая ситуация по- вообще трудно поддается обработке в рамках С++ и приводит к устойчивому падению программы, что также является надежным и легко диагностируемым способом поиска ошибки.

Алгоритм построения графа системы и топологической сортировки по предъявленным источникам и приемникам основан на поиске в ширину [@Cormen2005] и состоит в следующем:

Алгоритм 1

 

 

Балансирование задержек

После топологической сортировки вершины графа хранятся в массиве, и верно следующее утверждение:

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

Таким образом, с точки зрения балансировки задержек представляют интерес вершины (фильтры), которые имеют несколько входов (так как одинаковой задержки надо добиться только для таких входов), на баланс задержек для этой вершины влияют только те вершины, которые имеют в массиве меньший индекс. Алгоритм балансирования может быть построен следующим образом.

Найти первую вершину со многими входами, найти пути ведущие к ней из источников и вычислить задержки. Если задержки по различным ветвям разные, то сбалансировать их, увеличивая задержку по ветвям, по которым задержка меньше. Пометить обработанные вершины. Затем можно приступить к обработке следующей вершины со многими входами. Обработка аналогична за исключением того, что если при прослеживании ведущих к ней путей находится помеченная ранее вершина, то этот путь прекращается, и делается пометка, что он связан с ранее обработанной областью.

 

 

 

Список литературы

  1. [@Cormen2005] Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ. 2-е издание. //Издательство: Вильямс, 2005 г. 1296 стр. ISBN 5-8459-0857-4, 0-07-013151-1
  2. [@Canny] Canny J. A computational approach to edge detection // IEEE Trans. PAMI. 1986. V. 8. P. 34-43.
  3. [@DiZenzo] Di Zenzo S. “A note on the gradient of multi-image”, Computer Vision Graphics Image Process, Vol. 33. pp. 116-125, 1986
  4. [@RSeg] Mintchenkov M.V., Yurin D.V., Helvas A.V. Unsupervised Algorithm for Images Segmentation on the Base of the Rayleigh 2D Objects Boundaries Detector. // In Conference Proc. 12-th International Conference on Computer Graphics GraphiCon'2002 -P. 243-250. Nizhny Novgorod, Sept. 16-21, 2002. http://www.graphicon.ru/2002/pdf/Mintchenkov_Re.pdf.
  5. [@Kraftsov] Кравцов А.A. ,Сидоркина О.C., Юрин Д.В. Модифицированный рэлеевский детектор слабоконтрастных границ двумерных объектов на изображении. // Труды конференции Графикон 2006, 16-я международная конференция по компьютерной графике и ее приложениям, ‑‑C.351-354.
  6. [@JSeg] Deng Y., Manjunath B.S., Shin H. Color Image Segmentation // IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR '99 — 1999 — V.2. — P.446–451. http://vision.ece.ucsb.edu/publications/99CVPRSeg.pdf.
  7. [@HSeg] Jing, F., Li, M., Zhang, H.J., Zhang, B. Unsupervised Image Segmentation Using Local Homogeneity Analysis. // Proc. IEEE International Symposium on Circuits and Sys-tems, 2003. http://citeseer.ist.psu.edu/jing03unsupervised.html
  8. [@Harris] C. G. Harris and M. Stephens, "A combined corner and edge detector," In Proc. 4th Alvey Vision Conf., Manchester, pages 147-151, 1988.
  9. [@Dufour] Y. Dufournaud, C. Schmid, and R. Horaud, "Matching images with different resolutions", Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR’00), 2000 (Hilton Head Island, SC, USA). ‑V. 1,  ‑P. 612-618. ISBN: 0-7695-0662-3. http://citeseer.ist.psu.edu/dufournaud00matching.html
  10. [@Lindeberg] Tony Lindeberg: Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, Dordrecht, Netherlands, 1994. См. также http://www.nada.kth.se/%7Etony/earlyvision.html.
  11. [@Schmid] C. Schmid, R. Mohr. Local Grayvalue Invariants for Image Retrieval. //IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 1997, ‑V. 19, ‑No. 5, ‑P.  530-534. http://citeseer.ist.psu.edu/schmid97local.html