Презентация на тему Введение в мультимедийные базы данных 10

растровые) изображения
m × n матрица пикселей
По k бит на

каждый пиксел - 2k возможных значений

Типы изображений:
Черно-белые изображения (черный = 0; белый = 1; например, телефакс)
Полутоновые изображения (обычно k = 8, что дает 256 уровней серого)
Цветные изображения (различные представления)

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

медицинские изображения)

Устройства, создающие цифровые изображения:
Сканер
Цифровая камера
Электронный микроскоп

Основные параметры:
Разрешение (частота дискретизации, количество пикселей на дюйм)
Точность (число бит на пиксел)

что дает 256 оттенков серого
Передача полутонов (halftoning) – имитация

уровней серого черным и белым
Стандартная технология печати: круглые точки разных размеров с равноотстоящими центрами

Цифровая передача полутонов:
С помощью шаблонов: каждый пиксел заменяется черно-белым шаблоном («шрифтом») с определенной пропорцией черного


Размывание (dithering): создание дополнительных цветов в изображениях с ограниченной цветовой палитрой; настройка значений соседних пикселей для создания нужных оттенков серого

Три компоненты (канала) на пиксел (плюс возможно 4-ый канал

– альфа-канал (α-channel) = информация о прозрачности)
RGB: Red (красный), Green (зеленый), Blue (голубой); обычно 3 x 8 = 24 бита на пиксел
CMY: Cyan (голубой), Magenta (пурпурный), Yellow (желтый); CMYK используется в цветной печати, где K (key) - черный
HSI: Hue (цвет), Saturation (насыщенность), Intensity (интенсивность); используется при обработке изображений
YUV: цвет задается одной яркостной компонентой Y и двумя цветовыми компонентами U и V; используется при сжатии изображений; используется в формате JPEG, телевизионном стандарте PAL
Информация о яркости отделена от информации о цвете
Большая часть информации заключена в Y-компоненте
Эффективна для сжатия изображений (JPEG)
Изображения с цветовой таблицей:
Информация о цвете хранится в отдельной таблице
Палитра из, например, 256 цветов
Отображение таблицы в RGB-значения
Уменьшение размера; достаточно для многих приложений

приложений и сред, среди них:
BMP: Windows Bitmap - растровое

изображение Windows
GIF: Graphics Interchange Format; включает сжатие (без потерь), для обмена графическими изображениями
JBIG: Joint Bi-level Image Experts Group; формат обмена графической информацией
JPEG: Joint Photographic Experts Group; сжатие (с потерями) фотографических изображений
PBM: Portable Bitmap Format; формат для черно-белых изображений; 1 бит на пиксел
PGM: Portable Greymap Format; для полутоновой графики; 8 бит на пиксел
PNG: Portable Network Graphics; замена GIF; сжатие без потерь
PPM: Portable Pixmap Format; для цветных изображений; 24 бита на пиксел
TIFF: Tagged Image File Format; для хранения изображений; гибкий и настраиваемый формат; множество опций

размера
Уменьшение времени передачи
Возможно в силу избыточности информации в изображениях
Несколько

методов, приспособленных для различных типов изображений
Основные этапы:
1. Моделирование
Определение распределения символов или блоков
2. Кодирование
Определение бинарных представлений для символов/блоков
На основе модели распределения
Алгоритмы: кодирование по алгоритму Хаффмана, арифметическое кодирование

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

в битах на пиксел
Скорость (отдельно для упаковки и распаковки)
Искажение (для методов с потерями):
MAE (mean absolute error): средняя абсолютная ошибка
MSE (mean squared error): среднеквадратическая ошибка
RMSE (root mean squared error): квадратный корень из MSE
SNR (signal to noise ratio): отношение сигнал-шум
PSNR (peak signal to noise ratio): отношение максимальный сигнал-шум
Ошибкоустойчивость (по отношению к потенциальным ошибкам во время передачи)
Для методов с потерями: появление границ между блоками (блок – группа из, например, 8х8 пикселей), размывание изображения и т.д.

потерь
Вероятность(белый) >> Вероятность(черный)
Однородные области одного цвета
Пример применения: телефакс

Различные

методы сжатия:
Метод RLE (run-length coding):
Построчная обработка, слева направо
«Серия» - последовательность пикселей одного цвета
Белые и черные серии чередуются
Длины серий кодируются с помощью, например, кода Хаффмана или с помощью заранее известной таблицы кодов

белые, кодируются 0, иначе 1
Несколько уровней блоков: самый нижний

уровень – непосредственно изображение
Аналогично иерархическому сжатию битовых строк (см. тему 6, «Битово-матричное индексирование»)
Но в данном случае, блоки бит – двумерные; деление на блоки как, например, в тетрарных деревьях
Пример:
пиксели ‘x’ можно не хранить

исходя из значений соседних пикселей (пиксели слева и сверху,

т.е. уже закодированные), определяется вероятность иметь черный или белый цвет
Используется в JBIG (Joint Bi-level Image Experts Group)
Более новый стандарт известен как JBIG2, предыдущий – JBIG1
Стандарт от ISO/IEC и ITU-T
Для «предсказания» используются 7-10 пикселей
Окончательное кодирование с помощью QM-coder [3] (двоичное арифметическое кодирование)
Типичный коэффициент сжатия – 20:1

пикселей
Наличие текстур усложняет процесс сжатия
Методы сжатия сильно отличаются от

методов для черно-белых изображений

(I) Сжатие без потерь:
Относительно редкое использование
Пример приложения: сжатие рентгенограмм
Типичный коэффициент сжатия – 2:1
Сжатие без потерь в JPEG (Joint Photographic Experts Group):
Основано на прогнозировании
Несколько вариантов возможных (предсказываемых) значений: a, b, c, (a+b)/2, a+b−c, b+(a−c)/2, a+(b-c)/2, ...
Кодируется (с помощью арифметического кодера) разница между реальным и «предсказанным» значениями пиксела

приложений
Коэффициент сжатия 10:1 обычно дает гарантию “неотличимости” сжатого изображения

от оригинала
Группы применяемых методов:

Квантование (quantization):
Как правило, не используется независимо - часть более сложных методов
Диапазон значений задается одним значением
Используются самые важные разряды в значениях пикселов

Прогнозирование:
Строится «разностное» изображение (в котором значение каждого пиксела равно разнице между реальным и предсказанным значениями этого пиксела), затем полученное изображение квантуется и только потом кодируется
DPCM - дифференциальная импульсно-кодовая модуляция (ДИКМ)

в 2x2 пикселя одним значением
Обычно часть других методов

Пирамидальная техника:
Итерационная

субдискретизация (блок пикселей заменяется одним пикселем с усредненным значением, получившееся изображение опять разбивается на блоки, заменяемые одним пикселом, и т.д.); в итоге, получаем одно значение (= усредненный уровень серого)
Получаемые (и хранимые) «разностные» изображения, в которых значение каждого пиксела равны разнице между реальным и усредненным по блоку значениями, позволяют восстановить оригинальное изображение
Своего рода обобщение иерархического блочного кодирования
Естественный подход для постепенного (progressive) отображения (передачи) графики: сначала отображение в плохом разрешении, затем последовательно все в более лучшем

пикселям или блоку в 4х4 пиксела) ставится в соответствие

вектор
Выбираются наиболее типичные вектора, которые помещаются в «кодовую книгу»
Создается (и кодируется) индекс, который каждому блоку ставит в соответствие определенный вектор из кодовой книги
Быстрая распаковка
Различные эвристики для формирования кодовой книги
Пример (блок – два соседние пиксела; двумерные вектора):

Полутоновая «Лена» Представление пар пикселов Два бита на пиксел Четыре бита на вектор
в двумерном пр-ве [0,0]-[255,255] (разбиение Вороного)
Взято - http://www.gamasutra.com/features/20010416/ivanov_01.htm

(DFT – discrete Fourier transformation)
Для изображений более распространено: дискретное

косинус-преобразование [1] (DCT)
Для блока N × N:






Стандарт JPEG:
DCT применяется к блоку 8 на 8 пикселей, что дает 64 коэффициента
Низкие (самые важные) частоты находятся слева вверху
Коэффициенты квантуются (с помощью матрицы квантования) и кодируются
Высокая эффективность и качество; возможность постепенного отображения (передачи) графики

DCT), но пространственное расположение
Разные семейства базовых вейвлет-функций (например, Хаара,

Добеши)
Дискретное вейвлет-преобразование (DFT) используется в новом стандарте JPEG 2000
JPEG 2000 превосходит JPEG

Фракталы:
Фрактал - структура, состоящая из частей, которые в каком-то смысле подобны целому
В некоторых изображениях (например, фотографиях природных объектов) части изображения могут быть похожими на другие части того же изображения
Могут достигаться очень высокие коэффициенты сжатия
Очень медленное сжатие, относительно быстрая распаковка
Не является реальным конкурентом JPEG

изображений
Простейшая идея: применить сжатие для полутонов к каждому из

цветов (красный, синий, зеленый)
Но тогда не будет учитываться высокая корреляция между цветами
Лучшая идея: преобразовать в YUV-модель цвета (сделано в JPEG)
Человеческий глаз наиболее чувствителен к яркости (компонента Y); компоненты цветности (U и V) менее важны и, значит, могут кодироваться менее точно (например, к ним можно применить субдискретизацию)
Изображения с цветовой таблицей:
Методы сжатия полутоновых изображений не подходят (значения цветов не являются непрерывными)
Можно использовать методы сжатия для ASCII-файлов
Пример формата: GIF [1]

изображений
При поиске пользователь использует иерархию, например:
Художественные произведения

Живопись
Россия
19-ый век

С помощью индекса признаков
Изображения рассматриваются как документы с индексом терминов

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

изображений
Извлечение описательных атрибутов из изображений
Вручную, автоматически или комбинированная схема

(автоматическое сегментация и ручное добавление свойств)

Ручное (неавтоматическое) индексирование:
Выполняется «экспертом», знакомым (обученным) с шаблонами (графическими образами) и словарем, которые используются в рассматриваемой базе данных изображений
Множество экспертов: строгие правила непротиворечивости, общий глоссарий
Распознавание образов может осуществляться автоматическими средствами
Каждый заслуживающий внимания объект (пространственная струкутура) дополняется описательными атрибутами и вводится в систему вручную
Помощь при выборе индексных терминов: иерархические словари, системы перекрестных ссылок, тезаурусы предметных областей
Времязатратно и дорого

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

и т.д.)
В начале, система должна быть «обучена», а объекты рассматриваемой предметной области упорядоченны по категориям
Допускается определенная степень неопределенности (нечеткости)
Важная область применения автоматического анализа изображений и распознавания объектов: преобразование бумажных документов в цифровую форму, и последующая индексация оцифрованных документов (→ электронные библиотеки)

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

p% пикселей связной области имеют определенный цвет (черный или

белый)
Полутоновые изображения со сгруппированными по значениям пикселями, например – 0..9, 10-19, и т.д.: связная область однородна, если как минимум p% ее пикселей относятся к одной группе значений
Динамическая классификация полутонов: значения для каждого из классов не задаются предварительно, вместо задается размер интервала – значения серого у p% пикселей должны быть в пределах δ единиц
Полутоновые изображения с заданной базовой функцией (для однородности): для как минимум p% пикселей рассматриваемой области верно grey_level(x, y) - f(x, y) < δ
Связная область:
Для каждой пары пикселей - (x1, y1), (xn, yn) существует последовательность пикселей из данной области {(x1, y1), ..., (xn, yn)} таких, что пиксели {(xi, yi), (xi+1, yi+1)} являются смежными (соседями) для любого i

на регулярные блоки:
Пример: разбиение пространства с помощью тетрарного или

двоичного дерева до тех пор пока не будут получены однородные области
Как правило, не удовлетворяется условие максимальности для сегментации: соседние блоки могут образовывать одну однородную область
Обобщение сегментации с помощью двоичного дерева: разбиение может производиться в любом направлении – сегментация на полигоны
Компромиссное решение: разбиение только в направлениях 0°, 45°, 90° и 135°

б) Разбиение и слияние:
Дополнение методов а) для выполнения условия максимальности
Попарная тестовая проверка полученных регионов на однородность
Обычно, сегментация для произвольного предиката однородности не является уникальной

набора затравочных (начальных) точек (seed points)
Наращивать однородные области, рассматривая

пиксели, примыкающие к (сначала) затравочным точкам и (далее) к растущим однородным областям
Основное затруднение: как выбирать затравочные точки?

г) Движение по контуру:
Движение по контуру объекта (области), которую предполагается обнаружить; контур можно определить, следуя вдоль наибольшего градиента (изменений в значениях уровня серого)

д) Сравнение с пороговым значением:
Применимо, если представляющие интерес объекты и фон изображения имеют достаточно отличающиеся значения уровней серого
Гистограмма значений серого для изображения имеет два или более пиков, между которыми можно выбрать пороговые значения для уровня серого
Должна быть, как правило, дополнена более сложными методами

базах данных изображений
Общее свойство:
Не стопроцентно точный поиск

Виды

запросов:
Найти изображения с определенными признаками (цвет, текстура, фигура и т.д.)
Найти изображения, содержащие определенный тип(-ы) объектов
Найти объекты (в изображениях) с определенными атрибутами, например, определенной фигуры (круг, треугольник и т.д.), размера, цвета и т.д.
Найти изображения, в которых объект типа А расположен слева от объекта типа Б (пространственное отношение)
Поиск по сходству: найти изображения (сегменты), похожие на заданное изображение (сегмент)
Приложения: распознавание/идентификация людей по фотографиям или по отпечаткам пальцев; распознавание военных объектов (самолетов, кораблей и т.д.)

поиска по сходству:
а) Метрический подход:
Вводится функция расстояния (метрическая функция)

для изображений (сегментов)
Задача: найти ближайшего соседа (k ближайших соседей) к заданному в запросе изображению (сегменту)
Простейшие метрические функция для m × n цветных изображений:
Сумма евклидовых расстояний между попарными значениями пикселей (в трехмерном пространстве)
Евклидово расстояние в (m × n × 3)-мерном пространстве
Требуется большой объем вычислений
Упрощение:
Для уменьшения размерности использовать извлечение признаков: например, применить DCT (см.«Сжатие изображений») и далее для вычисления расстояний использовать полученные коэффициенты; новая метрическая функция d’ должна удовлетворять (приблизительно) условию: d’(a, b) < d’(a, c), если d(a, b) < d (a, c)

видов метрического подхода
Основная идея: степень несходства пропорциональна минимальной «цене»

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

(IBM's Query By Image Content)
Поиск по содержимому изображений
Извлечение признаков

при наполнении базы данных:
Расположение цветов/текстур
Идентификация объектов: ручная, полуавтоматическая, автоматическая сегментация
Графически задаваемые запросы, основанные на:
Изображениях-образцах
Набросках, эскизах, введенных пользователем (параметры фигур)
Цветах (основной цвет или цветовая гистограмма)
Структуре текстур (крупнозернистость, контраст, направленность)
Движении камеры или объекта (для видео)
Быстрый поиск:
Фильтрация и индексация
Уменьшение размерности с помощью преобразований (индексация на основе R*-дерева)

(возможно в сжатом виде), занимающей в большинстве случаев несколько

дисковых страниц
Каждое изображение можно рассматривать как один самостоятельный файл

а) Реляционное представление:
Представление изображения: идентификатор изображения и его основные свойства (атрибуты)
Представление объекта: объекты (сегменты, прямоугольники) внутри изображений; извлекаются вручную или автоматически
Атрибуты включают: id изображения, id объекта, координаты минимального ограничивающего прямоугольника, признаки
Обобщение: вероятностные отношения - объект x находится в изображении i с вероятностью p
Запросы: применять стандартную технику запросов, используя значения признаков в условиях запроса

помощью R- или R*-деревьев
Построить одно R-дерево для всех изображений

в базе данных
Страница, соответствующая листу, содержит близко-расположенные объекты (их MBR’ы) со списком указателей на исходные изображения
Также сохранены дополнительные свойства (признаки) объекта
Для не пространственных свойств объектов может быть построен отдельный индекс

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

для изображений

ниже полутоновому изображению размером в 4 на 4 пикселя.

Затем восстановить (раскодировать) изображение. Диапазон значений серого – 0..255. Кодирование в двоичные значения опустить.



Для приведенного ниже полутонового изображения произвести сегментацию на регулярные блоки (разбиение с помощью, например, тетрарного дерева). Далее, проверить соседние области на однородность и слить, где возможно. Область однородна, если разница между наибольшим и наименьшим значением пиксела не более 10.