Алгоритм и программа совмещения изображений были разработаны в качестве дипломного проекта «Алгоритм совмещения цветовых компонент фотографических изображений» по специальности «Информатика» Белорусского государственного университета информатики и радиоэлектроники. Ниже приводится та часть отчета, которая касается разработки алогоритма и программы совмещения.


Содержание
Введение
Анализ задачи
Анализ предметной области
Анализ возможных решений
Постановка задачи
Выбор алгоритма совмещения
Алгоритм совмещения по треугольникам
Алгоритм совмещения по четырем опорным точкам
Получения цвета пикселя
Архитектура системы
Анализ требований области приложения
Выбор средств разработки
Интерфейс системы
Реализация алгоритмической части
Реализация
Форматы файлов растровой графики
Библиотека чтения и записи изображений
Реализация алгоритма совмещения
Заключение
Список использованных источников


Введение


На протяжении 1909–19012 гг., а затем в 1915 г. Сергей Михайлович Прокудин–Горский (1863–1944) фотографировал наиболее интересные явления общественной жизни, культурные памятники, заводы, мосты, интересные типажи — все то, что, по его мнению, могло представить интерес для потомков.


Прокудин–Горский родился во Владимире в 1863 году и по образованию был химиком. Всю свою деятельность он посвятил развитию фотографии. Он учился у известных ученых в Санкт–Петербурге, Берлине и Париже. В результате своих оригинальных исследований Прокудин–Горский получил патенты на производство цветных диапозитивов и проектирование цветных фильмов. В 1908 году Прокудин–Горский задумал и разработал план использования новых технологических достижений, сделанных в цветной фотографии, для систематической фотодокументации Российской Империи. Хотя этот проект казался очень смелым, конечной целью Прокудина–Горского было ознакомление школьников России с огромной и разнообразной историей, культурой и модернизацией Империи при помощи его «оптических цветных проекций». Получив в распоряжение от царя Николая II специально оборудованный железнодорожный вагон с темной комнатой и имея на руках два разрешения, обеспечивающих ему доступ в запретные зоны и содействие со стороны бюрократических кругов Империи, Прокудин–Горский провел фотообзор Российской Империи с 1907 по 1915 год и прочитал много лекций, иллюстрируя свою работу.


Прокудин–Горский придумал свою схему передачи цветовой палитры: фотосъемка одного и того же объекта производилась три раза, через разные цветовые фильтры (красный, зеленый и синий). Каждый фильтр пропускал только определенный диапазон спектра. В результате после проявки на каждой пластине оказывалась запечатленной только своя часть спектра. После проявки на каждой фотографической пластине оказывалось черно-белое представление одного из трех цветов. Затем, используя систему проекции света с теми же самыми тремя фильтрами, он показывал эти изображения в цветном варианте на диапозитивах на лекциях.


В 1918 г. Прокудин–Горский уехал из России, выполнив 1906 фотографий в цвете и около 600 черно-белых фотографий.


В 1944 г. Сергей Михайлович Прокудин–Горский умер в Париже, а в 1948 г. пластины были куплены у его наследников библиотекой конгресса США. С тех пор пластины хранятся там.


Несколько лет назад пластины были отсканированы и выложены в Internet для свободного доступа. Это является правомерным шагом, так как после смерти их владельца прошло более 50 лет, и все авторские права на них принадлежат общественности. Все три цветовых компонента хранятся в одном файле в формате TIFF с глубиной цвета 16 бит. Первую треть файла занимает цветовая компонента синего цвета, вторую — зеленого, и третью — красного цвета. Общий размер файла составлял около 75М. Размер одной цветовой составляющей в пикселях составляет около 3500 по ширине и высоте.


Качество отсканированных изображений достаточно высоко, чтобы использовать их в печати. Поэтому в Издательстве Белорусского Экзархата было принято решение скачать все файлы, совместить изображения и издать серию альбомов под предположительным названием «Цвета Российской империи». Примерно через полтора года все изображения были скачаны Издательством.


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


Анализ задачи


Анализ предметной области


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


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


Преобладание в световом потоке какой-либо составляющей определяет его цветовой оттенок. Полное отсутствие всех составляющих (0, 0, 0) — это черный цвет, 100% всех составляющих (255, 255, 255) — белый цвет. Какой-либо отличный от черного цвет образуется добавлением о количества составляющих, поэтому модель называется аддитивной. Реальные характеристики черного и белого (границы диапазона) зависят как от источника света, так и от приемника. Сканер, цифровая камера, монитор, как и человеческий глаз, воспринимают цвет именно таким способом.


При печати используется цветовая модель CMYK. Бумага отражает белый поток света, и для восприятия цветного изображения необходимо регулировать цветовые составляющие света, то есть избирательно удалять из потока отдельные составляющие (R, G и B). В результате многочисленных исследований была созданы краски C, M и Y, дополнительные к R, G, B. При увеличении количества С уменьшается количество R, чем больше M и Y, тем меньше G и B соответственно. Эта система, основанная на вычитании цветов, называется субстрактивной.


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


Описанные выше модели сильно зависят от конкретного устройства-интерпретатора. Поэтому была создана аппаратно-независимая система исчисления цвета — Lab, привязанная к объективной цветовой характеристике — длине волны. Ee три параметра (канала): Lightness (светлота) и две специфические координаты для оттенков цвета a и b. Все пересчеты из модели в модель в пакетах-цветоделителях осуществляются через Lab.


Эти три модели являются самыми распространенными, но кроме них существует еще множество других моделей представления цвета.


Модель Grayscale представляет оттенки серого, чаще всего используется для передачи монохромных изображений. Все многоканальные изображения (Lab, CMYK, RGB) состоят из нескольких Grayscale-каналов, каждый из которых представляет отдельный цвет.


Битовая карта Bitmap использует всего один бит для пикселя. Пиксель может быть либо черным, либо белым. Очень хорошо подходит для черно-белой графики (тушь, перо). Этот способ является самым легким, но требует высокого разрешения — не менее 600 dpi.


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


Формат Indexed Color является попыткой максимально облегчить файл, работая только с 256-ю цветами. В основном применяется в web-дизайне [1].


Сложность задачи определятся тем, что цветовые компоненты фото-графий нельзя механически наложить друг на друга. За счет смещений светочувствительных пластинок при фотографировании, небольших поворотов фотоаппарата, движения фотографируемого объекта, погрешностей при сканировании цветовые компоненты не точно соответствуют друг другу. Поэтому в полученном механическим совмещением изображении цвета оказываются смещенными, растянутыми, повернутыми друг относительно друга. Величина смещения или растяжения компонент может достигать 350 пикселей, что составляет одну десятую величины изображения. Величина поворота может достигать 15 градусов.


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


Возникла необходимость такого совмещения цветовых компонент, которое позволило бы получить полноценное четкое цветное изображение. Инструментарий Adobe Photoshop позволяет корректно совмещать изображения, но при его использовании время обработки одного изображения составляет примерно 30 минут, причем на протяжении всего времени требуется значительное зрительное напряжение оператора. Время совмещения всех 1906 цветных изображений составило бы 953 человеко-часа, или около пяти месяцев при восьмичасовом рабочем дне. Это не очень большой промежуток времени, но с учетом крайне большой зрительной нагрузки сохранение здоровья и работоспособности оператора обуславливает снижение производительности до 4 изображений в день. При такой скорости работы совмещение заняло бы около двух лет. Это неприемлемо большой срок.


Было решено написать программу, которая могла бы совмещать цветовые компоненты в несколько раз быстрее и которая при этом не требовала бы длительного зрительного напряжения.


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


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


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


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


Наиболее популярной классификационной схемой, единообразно описывающей все многообразие существующих методов совмещения, является схема, включающая в себя три характеристики: пространство поиска или допустимое пространственное преобразование и преобразование яркости между изображениями, тип применяемых характерных элементов изображения и стратегия поиска оптимального решения. Эти три характеристики не являются независимыми. Так, выбор конкретных характерных элементов изображения заметно сужает возможное пространство поиска, а эти две характеристики совместно во многом определяют стратегию поиска [2].


Анализ возможных решений


Существует несколько способов решения проблемы совмещения изо-бражений.


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


Технически это состоит в создании многослойного персептрона, на вход которого последовательно подавались бы три изображения. После обработки на выходах персептрона оказались бы координаты общих областей изображений. После этого общие области можно было бы совместить, используя, например, метаморфические преобразования или преобразования Хафа [3].


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

  1. Распознавание таких сложных образов, как фотографии Прокудина-Горского, с помощью многослойного персептрона даже в настоящее время является мало исследованной методикой. Не найдено универсального алгоритма создания и обучения персептрона, который мог бы распознавать столь большие изображения с высокой точностью и приемлемой скоростью.
  2. Можно ожидать, что суммарное время обучения персептрона для всех изображений окажется неприемлемо большим.
  3. Наличие на изображении царапин, вмятин, артефактов, возникших при проявке фотографического стекла с помощью несовершенных технологий начала XX в. еще более усложняет процесс распознавания.
  4. Недостаточная компетентность автора в вопросах искусственного интеллекта и распознавания образов.


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


Тем не менее, данный способ по указанным выше причинам далее не рассматривается.


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


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


Существует один известный автору аналог программы — программа для совмещения аэро- и космоснимков и карты местности. Программа преобразует фотоснимок, линейно интерполируя треугольники, полученные в ходе работы одного из реализованных в программе методов (триагуляция Делоне и метод рекурсивного случайного деления треугольников). Так как объем работы для этой программы невелик и так как нужна большая тщательность при совмещении снимков и карты, то большие затраты времени оператора на ввод опорных точек являются оправданными [4].


Постановка задачи


После проведенного анализа решений для реализации были выбраны два способа — интерполяция по треугольникам с использованием алгоритма триангуляции Делоне и интерполяция по четырем опорным точкам.


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


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


Выбор алгоритма совмещения


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


Алгоритм совмещения по треугольникам


Алгоритм совмещения по треугольникам предполагает наличие большого количества точек. Он представляет собой линейную интерполяцию точек внутри каждого треугольника.


Для построения треугольников используется инкрементальный алго-ритм построения триангуляции Делоне.


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


Все точки из набора S могут быть подразделены на граничные точки — те точки, которые лежат на границе выпуклой оболочки S, и внутренние точки — лежащие внутри выпуклой оболочки S. Также можно классифицировать и ребра, полученные в результате триангуляции S, как ребра оболочки и внутренние ребра. К ребрам оболочки относятся ребра, расположенные вдоль границы выпуклой оболочки S, а к внутренним ребрам — все остальные ребра, образующие сеть треугольников внутри выпуклой оболочки. Отметим, что каждое ребро оболочки соединяет две соседние граничные точки, тогда как внутренние ребра могут соединять две точки любого типа. В частности, если внутреннее ребро соединяет две граничные точки, то оно является хордой выпуклой оболочки S. Заметим также, что каждое ребро триангуляции является границей двух областей: каждое внутреннее ребро находится между двумя треугольниками, а каждое ребро оболочки — между треугольником и бесконечной плоскостью.


Любой набор точек, за исключением некоторых тривиальных случаев, допускает более одного способа триангуляции. Но при этом существует замечательное свойство: любой способ триангуляции для данного набора определяет одинаковое число треугольников, что следует из теоремы о триангуляции набора точек: предположим, что набор точек S содержит n > 3 точек и не все из них коллинеарны. Кроме того, i точек из них являются внутренними (т. е. лежащими внутри выпуклой оболочки S. Тогда при любом способе триангуляции набора S будет получено точно n + i - 2 треугольников.


Алгоритм работает путем постоянного наращивания текущей триангуляции по одному треугольнику за шаг. Вначале текущая триангуляция состоит из единственного ребра оболочки, по окончании работы алгоритма текущая триангуляция становится триангуляцией Делоне. На каждой итерации алгоритм ищет новый треугольник, который подключается к границе текущей триангуляции.


Определение границы зависит от следующей схемы классификации ребер триангуляции Делоне относительно текущей триангуляции. Каждое ребро может быть спящим, живым или мертвым:

  1. спящие ребра: ребро триангуляции Делоне является спящим, если она еще не было обнаружено алгоритмом;
  2. живые ребра: ребро живое, если оно обнаружено, но известна только одна примыкающая к нему область;
  3. мертвые ребра: ребро считается мертвым, если оно обнаружено и известны обе примыкающие к нему области.


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


На каждой итерации выбирается любое одно из ребер е границы и оно подвергается обработке, заключающейся в поиске неизвестной области, ко торой принадлежит ребро е. Если эта область окажется треугольником f, определяемым концевыми точками ребра е и некоторой третьей вершинов v, то ребро е становится мертвым, поскольку теперь известны обе примыкающие к нему области. Каждое из двух других ребер треугольника t переводятся в следующее состояние: из спящего в живое или из живого в мертвое. Здесь вершина v будет называться сопряженной с ребром е. противном случае, если неизвестная область оказывается бесконечной плоскостью, то ребро е просто умирает. В этом случае ребро е не имеет сопряженной вершины [5].


Перед началом работы алгоритма пользователь вводит точки, используя разработанный интерфейс. Точки устанавливаются на характерные пиксели изображения, для которых оператор может легко определить точное соответствия. Число точек не должно быть меньше трех-четырех, а для достижения высокого качества совмещения необходимо расставить 30–50 точек на каждой из цветовых компонент.


Формируется массив точек, который содержит усредненные значения координат. Эти координаты считаются «правильными», именно в них будут отображены введенные пользователем точки после работы алгоритма. Участки изображения между «правильными» точками будут искажены с учетом смещения точек цвета относительно усредненных.


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


Текущая точка внутри треугольника разбивает его на три новых тре-угольника. Усредненные вершины треугольника обозначим символами A, B, C, а текущую точку — символом I. Тогда смещение текущей точки относительно ее координат можно вычислить по формуле:


формула 1


Аналогично вычисляется и смещение по координате y. Все три цветовых компоненты преобразуются аналогично. Точки на границах треугольников преобразуются аналогично точкам внутри треугольников.


После вычисления смещения можно вычислить и значения результирующих координат точки. Для этого к исходным координатам точки добавляется ее смещение.


Метод совмещения по треугольникам имеет как достоинства, так и недостатки. К достоинствам метода можно отнести очень высокое качество совмещения.


Метод совмещения по треугольникам имеет следующие недостатки:

  1. Для достижения хорошего качества совмещения оператору необходимо расставить много — около 30 — опорных точек. Учитывая тот факт, что на одну точку уходит около минуты времени оператора, получим те же 30 минут, которые необходимы для совмещения средствами Photoshop, но для каждой цветовой компоненты. Этот недостаток делает разработку и использование программного обеспечения для совмещения изображений неоправданными.
  2. Так как интерполяция линейна, на результирующем изображении заметен излом изображения на границах треугольников, по которым производилась интерполяция. Для преодоления этого недостатка необходимо увеличивать число опорных точек, что еще более повышает трудоемкость совмещения сказывается на времени работы оператора.
  3. Преобразование не является линейным в пределах всего изображения. В худшем случае это может вызвать искажение пропорций изображаемого объекта.


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


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


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


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


Алгоритм совмещения по четырем опорным точкам


Для совмещения был разработан алгоритм совмещения по четырем опорным точкам.


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


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


В основе алгоритма лежит линейная интерполяция одного выпуклого четырехугольника к другому.


В начале работы алгоритм проверяет, является ли четырехугольник выпуклым. Для проверки ищется выпуклая оболочка четырехугольника по методу «заворачивания подарка».


Этот алгоритм обводит множество точек линией, «заворачивая» их в выпуклую оболочку. Алгоритм ищет нижнюю правую точку. После этого он ищет точку с наименьшим углом отклонения от горизонтали. Если таких точек несколько, то алгоритм выбирает точку, расстояние до которой максимально. После этого алгоритм ищет точку с наименьшим углом отклонения от прямой, проведенной через две предыдущие точки. Поиск продолжается, пока алгоритм не придет к начальной точке [6].


Этот алгоритм использовался в методе совмещения по треугольникам для отыскания выпуклой оболочки множества опорных точек. Для определения факта выпуклости четырехугольника можно было бы использовать ориентацию треугольников, входящих в его состав. Это более быстрый метод, но так как время работы алгоритма «заворачивания подарка» ничтожно по сравнению со временем обработки всех точек изображения и так как сроки разработки были ограничены, то было решено не менять алгоритм для ускорения разработки.


Если четырехугольник не выпуклый, то алгоритм завершает работу.


После алгоритм находит точки пересечения противоположных сторон четырехугольника. Здесь же проверяется, параллельны ли стороны, так как это влияет на ход вычислений. Обозначим точки эталонного четырехугольника символами A, B, C, D, а точки пересечения прямых AD и BC, AB и СВ — символами U и V соответственно. Текущую точку обозначим символом I.


Для каждой точки эталонной компоненты изображения выполняются следующие действия:

  1. Найдем точку пересечения прямых IU и AB. Обозначим ее М.
  2. Найдем отношение длин отрезков МA и AB. Обозначим это отношение k1.
  3. Аналогично, найдем точку пересечения прямых IV и BC. Обо-значим ее символом N.
  4. Найдем отношение длин отрезков BN и BC. Обозначим его k2.


При выполнении шагов 1 и 3 необходимо учитывать факт параллельности прямых AD и BC, AB и CD соответственно. Если соответствующие прямые параллельны, то точки U или V не определены. Тогда в пункте 1 необходимо искать не точки пересечения прямых IU и AB, а точки пересечения прямой AB и прямой, проходящей через точку I параллельно сторонам АD и CD, а в пункте 3 точку пересечения прямой BC и прямой, проходящей через точку I параллельно AB и CD.


Описанные четыре пункта выполняются только для синей составляю-щей изображения. После отыскания отношений k можно найти координаты точки на результирующем изображении, соответствующие текущей точке I.


Обозначим теперь символами A, B, С, D вершины четырехугольника на одной из преобразуемых компонент, а пересечения его сторон — U и V. Найдем точки, которые делят стороны AB и CD в соотношениях k1 и k2. Обозначим их M и N соответственно. Теперь найдем точку пересечения прямых UM и VN. Координаты полученной точки на преобразуемой компоненте соответствуют координатам точки на эталонной составляющей.


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


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


алгоритм совмещения изображений


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


Благодаря небольшому числу точек время обработки оператором одного изображения сравнительно невелико — около четырех минут. Это позволяет с большой скоростью обрабатывать изображения. Кроме того, качество результирующего изображения является по-прежнему достаточно высоким. Алгоритм не привносит никаких дополнительных артефактов или дефектов в изображение.


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


Кроме того, недостатком является невысокая скорость преобразования, так как при получении длины отрезка, выполняемого несколько раз для каждой точки, используется операция извлечения квадратного корня. Время преобразования программой одного изображения составляло около 5 минут.


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


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


Получения цвета пикселя


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

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


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


Существует несколько методов взвешивания цвета пикселей:

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


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


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


Архитектура системы


Архитектура программы или вычислительной системы — это структура системы, которая включает в себя программные элементы, свойства программных элементом, видимые извне, и отношения между элементами. Элементы, видимые извне — это те элементы системы, которые представляют сервисы, обработку ошибок, управление разделяемыми ресурсами и так далее [7].


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


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


Итеративная разработка — это такой подход к созданию программного обеспечения (или чего-либо иного), в котором общий цикл состоит из нескольких последовательных итераций. Каждая итерация — это самодостаточный мини-проект, в которой входят анализ требований, проектирование, разработка, программирование и тестирование. Цель каждой итерации — выпуск готового продукта этой итерации — стабильной, интегрированной и частично законченной системы [8].


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


Анализ требований области приложения


Итак, необходимо свести воедино все известные требования к разрабатываемой программе.


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


Декомпозиция основной задачи позволяет выделить две основных подзадачи:

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


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


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


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


Таким образом, были сформулированы следующие основные требования к программе:

  1. Программа должна предоставлять интерфейс для ввода точек, который является удобным и минимизирует зрительные усилия пользователя.
  2. Программа должна выполнять совмещение изображения на основе опорных точек. Реализация алгоритма должна совмещать высокое качество совмещения и большую скорость работы.
  3. Архитектура программы должна предусматривать легкую смену ал-горитмической части при неизменной интерфейсной.
  4. Программа должна предусматривать отложенную обработку изображений в пакетном режиме.


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


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


Выбор средств разработки


В качестве средства разработки был выбран Microsoft Visual C++. Эта среда обеспечивает удобное создание приложения, не усложняя обращения к функциям операционной системы и не ограничивая сознание программиста уже готовыми компонентами и средствами, как например Borland C++ Builder или Borland Delphi. Кроме того, язык программирования C++ широко применяется для разработки приложений, использующих функции операционной системы. Далее, было бы естественно предположить, что производитель операционной системы лучше владеет информацией о ее функциях, и потому реализовал лучшее средство разработки, чем сторонние организации.


Интерфейс системы


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


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


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


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


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


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


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


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


После ввода точек интерфейс позволял сохранить точки в файле.


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


Реализация алгоритмической части


Часть системы, которая выполняла собственно совмещение, была реализована в виде утилиты командной строки с возможностью ее взаимодействия с интерфейсом системы.


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


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


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


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


Реализация


Форматы файлов растровой графики


Основой растрового представления графики является пиксел (точка) с указанием ее цвета. Изображение представляется в виде большого количества точек — чем их больше, тем визуально качественнее изображение и больше размер файла. Для растровых изображений наибольшее распространение получили форматы .tif, .gif, .jpg, .png, .bmp.


Формат ВМР (Windows Device Independent Bitmap) является родным форматом Windows, он поддерживается всеми графическими редакторами, работающими под ее управлением. Он используется для хранения растровых изображений, предназначенных для использования в Windows Способен хранить как индексированный (до 256 цветов), так и RGB-цвет (16.700.000 оттенков). Характерным недостатком данного формата является большой размер файлов из-за отсутствия сжатия изображения.


Разработанный фирмой CompuServe для передачи растровых изображений по сетям, формат GIF (CompuServe Graphics Interchange Format) не зависит от аппаратного обеспечения. Он позволяет хорошо сжимать файлы, в которых много однородных заливок. GIF-формат позволяет записывать изображение «через строчку» (Interlaced), благодаря чему, имея только часть файла, можно увидеть изображение целиком, но с меньшим разрешением. Эта возможность широко применяется в Интернете. Сначала вы видите картинку с грубым разрешением, а по мере поступления новых данных ее качество улучшается. Основное ограничение формата GIF состоит в том, что цветное изображение может быть записано только в режиме 256 цветов. Для полиграфии этого явно недостаточно.


Формат хранения растровых изображений JPEG (Joint Photographic Experts Group) использует алгоритм сжатия JPEG. Этот алгоритм ищет плавные цветовые переходы в квадратах 9 на 9 пикселов. Вместо действительных значений JPEG хранит скорость изменения цвета от пиксела к пикселу. Лишнюю, с его точки зрения, цветовую информацию он отбрасывает, усредняя некоторые значения. Чем выше уровень сжатия, тем больше данных отбрасывается и тем ниже качество. Используя JPEG, можно получить файл в 10-500 раз меньше, чем ВМР. Алгоритмом JPEG лучше сжимаются растровые картинки фотографического качества, чем логотипы или схемы: в них больше полутоновых переходов, среди же однотонных заливок появляются нежелательные помехи.


PNG (Portable Network Graphics) — недавно разработанный формат, ориентированный на применение в сети и призванный в этом качестве заменить собой GIF. Использует сжатие без потерь. Глубина цвета может быть любой, вплоть до 48 бит (RGB, для сравнения, — 24), поддерживается плавно переходящая прозрачность. В файл формата PNG записывается информация о гамма-коррекции. Гамма представляет собой некое число, характеризующее зависимость яркости свечения экрана вашего монитора от напряжения на электродах кинескопа. Это число, считанное из файла, позволяет ввести поправку яркости при отображении. Таким образом, эта особенность помогает реализации основной идеи WWW — одинакового отображения информации независимо от аппаратуры пользователя [9].


Аппаратно независимый формат TIFF (Tagged Image File Format) на сегодняшний день является одним из самых распространенных и надежных, его поддерживают практически все программы, так или иначе связанные с графикой. TIFF является лучшим выбором при импорте растровой графики в векторные программы и издательские системы. Ему доступен весь диапазон цветовых моделей от монохромной до RGB и CMYK. К достоинствам формата TIFF относятся:

  1. TIFF способен отображать двухуровневые изображения, градации серого, собственную палитру цветов для изображения, полноцветные изображения и несколько цветовых пространств;
  2. TIFF включает в себя большое число схем сжатия, которые позво-ляют разработчикам выбирать наилучшую среду для приложений;
  3. TIFF не привязан к аппаратному обеспечению;
  4. TIFF легко переносим. Он поддерживает конкретную операцион-ную систему, файловую систему, компилятор или процессор;
  5. в формате TIFF предусмотрены расширения;
  6. TIFF позволяет включать в себя неограниченное количество ча-стной или проблемно-зависимой информации.


Формат TIFF не привязан к какой-либо модели представления цвета, он может хранить любое количество цветовых каналов с любой глубиной цвета [10].


Так как этот формат стал стандартом de facto в обработке промышленных растровых изображений, то исходные и преобразованные изображения хранятся именно в этом формате.


Библиотека чтения и записи изображений


Так как преобразуемые фотографии хранятся в формате TIFF, необходима библиотека для чтения и записи изображений. Была использована свободно распространяемая библиотека с открытым исходным кодом libtiff. Она предназначена для чтения и записи изображений в формате TIFF версий 4.0–6.0 и поддерживает около десяти алгоритмов сжатия.


Библиотека предоставляет средства для легкого доступа и создания TIFF файлов.


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


В процессе работы программы необходимо выполнять следующие операции с TIFF файлами:

  1. разархивирование и чтение массива точек из файла;
  2. получение размера изображения;
  3. выделение цветовых компонент точки;
  4. запись нового файла.


...


Реализация алгоритма совмещения


Для эффективности разработки и отладки были введены следующие структуры данных:

  1. Класс Point, представляющий точки в декартовых координатах.
  2. Кольцевой список, используемый в методе нахождения выпуклой оболоч-ки


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


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


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


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


Синяя составляющая остается неподвижной, а остальные две — красная и зеленая — приводятся к ней.


Для инициализации массива «правильных» опорных точек вызывается функция combine, которая и выполняет операцию совмещения. На вход функции подается два указателя — на область памяти, выделенную под исходное изображение, и на область памяти, куда будет записано совмещенное изображение, — а также высота, ширина и глубина цвета изображения, координаты точек, определяющих преобразуемый прямоугольник на исходных компонентах.


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


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


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


Затем начинается цикл по всем точкам результирующего изображения.


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


После формирования результирующего изображения функция combine завершает свою работу.


Затем полученное совмещенное изображение записывается в файл с помощью средств библиотеки libtiff. При записи для простоты указывается прямой порядок следования строк изображения в TIFF файле. Это также несколько уменьшает время работы утилиты.


После сохранения готового изображения утилита завершает свою работу.


Заключение


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


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


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


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


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


Разработанная программа не требует больших ресурсов — оперативной памяти, процессорного времени или времени оператора. Ввод опорных точек, используемых для совмещения, занимает около четырех минут, еще около минуты требуется для выполнения совмещения.


С помощью этой программы были совмещены все 1906 фотографий. В настоящее время к изданию готовится альбом, в котором будут представлены наиболее интересные фотографии. Планируется выпустить несколько тематических альбомов.




Список использованных источников


  1. Основы цвета, http://www.nadprof.ru/school/polygraph/4.shtml.
  2. Совмещение изображений, www.aicommunity.org/reports/Inex/ Im-ageSuperposition/ImageSuperposition.php?fid=64.
  3. Персептрон
  4. Программа совмещения изображений, loi.sscc.ru/hpc/statji/efim.htm
  5. Алгоритм триангуляции Делоне, algolist.manual.ru
  6. Gift Wrapping, algolist.manual.ru/maths/geom/convhull/gift.php
  7. Software Architecture in Practice, Second Edition, network edition, Len Bass, Paul Clements, Rick Kazman
  8. Agile and Iterative Development: A Manager's Guide, network edition, Craig Larman
  9. Основы растровой графики, do.rksi.ru/library/courses/ipsvs/tema2_2.dbk
  10. TIFF Specification, revivion 6, June 3, 1992, electronic edition, ftp://ftp.adobe.com/pub/adobe/DeveloperSupport/TechNotes/PDFfiles/TIFF6.pdf .
  11. LibTiff docementation, ftp://ftp.sgi.com/graphics/tiff/ .
  12. Физиология человека, под редакцией Шмидта Р. И Г. Тевса, тт. 1,3, Москва, «Мир», 1996 г.