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

Рассмотрим пример алгоритма сжатия изображений, который нацелен на уменьшение размера изображения путем поиска повторяющихся фрагментов в нем. Таким образом, ROBDD может оказаться удобной структурой данных для представления сжатых изображений. Вызывает интерес реализация такого метода сжатия изображений на основе ROBDD и сравнение его с другими комбинаторными методами, например  методом квадродеревьев и др. Для представления изображения в виде ROBDD нужно выделить булеву функцию для заданного изображения. М. Старки и Р. Брайант в статье “Using OBDD for compressing images and image sequences” предложили представить изображение функцией своих координат, т.е. закодировать все пиксели изображения на плоскости булевыми векторами.

 

                      

Рис. 4.4

 

На рис. 4.4 изображены простое черно-белое изображение размером 4х4 и координаты его пикселей. Для построения ROBDD выбираем порядок переменных p = { Х₀, Y₀, Х₁, Y₁}. Полученная ROBDD представлена на рис. 4.5.

 

                                                    

Рис. 4.5

 

Если расширить диапазон терминальных значений, то с помощью ROBDD можно представлять и цветные изображения. Метод наиболее эффективен для квадратных изображений. Если высота W и ширина H изображения различны, то метод также применим. В этом случае находится наибольшая координата, прямоугольник достраивается до квадрата, внешние пиксели закрашиваются некоторым фоновым цветом.

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

 

               

Рис. 4.6

 

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