Linuxformat - Вклад участника [ru]

LXF136:Стеганография

2014-04-22T08:50:57Z

Mike2014: ссылка на автора

: '''Стеганография''' Скрываем ценные данные в обычных на вид изображениях

==''Perl'': Водяные знаки==

{{Цикл/Perl}}[[Категория:Учебники]][[Категория:Perl]]

: '''Часть 3''': Тот, кто придумал выражение «вилами на воде писано», явно не знал про стеганографию и не читал статьи [http://www.smirnov.sp.ru/ '''Михаил Смирнов'''].

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

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

Наибольшей популярностью пользуется встраивание водяных знаков с регулируемой прозрачностью. С одним из вариантов такого встраивания мы уже познакомились в первой статье цикла ([[LXF134:Perl|LXF134]]). Удаление видимых графических знаков может вылиться в весьма сложную и трудоемкую задачу, и это следует отнести к достоинствам. Недостатки встраивания видимых водяных знаков, как ни парадоксально, состоят в их видимости. Последнее обстоятельство широко используется в подпольной индустрии контрафактной продукции для тиражирования подделок изображений известных торговых брендов.

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

===Двоичные водяные знаки===

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

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

===Метод битовых плоскостей===

{{Врезка|Содержание=[[Изображение:LXF136_64_1.jpg|300px|Рис. 1]] Рис. 1. Двоичные данные в битовой плоскости изображения.|Ширина=300px}}

Одним из наиболее известных способов сокрытия данных (водяных знаков) в цифровом изображении является метод встраивания в битовые плоскости изображения. Битовые плоскости или срезы – это просто разряды цифрового изображения, находящиеся в одних и тех же положениях в соответствующих двоичных числах, представляющих собой данные изображения. Их «веса» равны 2M, где M = 0,1,2, … – номер позиции. Алгоритм встраивания основывается на свойствах зрительного восприятия и реализуется таким образом, чтобы внедряемые биты оставались бы незаметными при визуальном рассмотрении цифрового изображения. Обычно для выполнения этого условия данные встраиваются в битовую плоскость с наименьшим весом, равным 20 (младший бит). Чем меньше вес выбранной битовой плоскости для встраивания, тем меньшее влияние оказывается на качество изображения-контейнера, и тем менее заметны изменения. На рис.1 представлен пример двумерной двоичной последовательности данных для сокрытия.

Объем '''Q''' символов встраиваемых данных в полутоновое [grayscale] изображение можно подсчитать по формуле: '''Q=P*W*H/B''', где '''P''' – число битовых плоскостей, используемых для встраивания, '''W''' и '''H''' – ширина и высота изображения в пикселях, соответственно, '''В''' — число бит на символ. На рис. 2 показаны примеры встраивания данных в битовые плоскости цветного (RGB) изображения.

{{Врезка|Содержание=[[Изображение:LXF136_65_1.jpg|500px|Рис. 2]] Рис. 2. Изображения со встроенными двоичными данными: а) в битовую плоскость нулевого разряда и только компоненты Blue, б) в четыре битовые плоскости всех RGB-компонент.|Ширина=500px}}

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

<source lang=perl>
$Width3 = $Width * $nbyte;
$wt = int($Width3/4);
$wt = $wt*4;
$ut = $Width3 - $wt;
if($ut!=0){$ut = 4 - $ut;}
for($j=0;$j<$Height; $j++){
for($i=0;$i<$Width; $i++){
bin[$i][$j] = int(rand(2));
}}
$bit_plan = 1;
$rgb=0;
for($j=0;$j<$Height; $j++){
$y1=$j*($Width3 + $ut);
$k=0;
for($i=$rgb;$i<$Width3; $i+=3){
$tmp = ($BMP_IMG[$i + $y1]>> $bit_plan)<< $bit_plan;
$BMP_IMG[$i + $y1] = $tmp + $bin[$k][$j];
$k++;
}
}
</source>

Исходное изображение-контейнер шириной '''$Width''' и высотой '''$Height''' пикселей содержится в массиве '''@BMP_IMG'''. В массиве '''@bin''' создается случайная последовательность двоичных чисел [0,1], имитирующих шифрованную последовательность скрываемых данных. Параметр '''$nbyte''' равен 3 для цветного RGB-изображения. В переменной '''$wt''' задается количество слов в строке изображения формата '''BITMAP'''. В переменную '''$tmp''' записывается результат обнуления битовой плоскости 20 синей компоненты ('''$rgb=0''').

Во втором примере, на рис.2б, для встраивания используются четыре битовых плоскости младших разрядов каждой из RGB-компонент соответственно. Из сравнения изображений на рис. 2а и рис. 2б видно, что чем больше битовых плоскостей занимают встраиваемые данные, тем выше степень искажений, видимых глазу. Причем, кроме отдельных шумовых выбросов, появляются ложные контуры на участках изображения с равномерным фоном (например, на голубом небе). Фрагмент программы для этого случая показан ниже.

<source lang=perl>
$bit_plan=4;
@BMP_IMG=map($_ >> $bit_plan, @BMP_IMG);
@BMP_IMG=map($_ << $bit_plan, @BMP_IMG);
for($plan=0;$plan<$bit_plan;$plan++){
for($rgb = 0;$rgb<$nbyte; $rgb++){
for($j=0;$j<$Height; $j++){
$y1=$j*($Width3 + $ut);
$k=0;
for($i=$rgb;$i<$Width3; $i+=3){
$BMP_IMG[$i + $y1] += $bin[$k][$j]*(1<<$plan);
$k++;
}}}}
</source>

Обнуление битовых плоскостей осуществляется вне основных циклов с помощью функции '''map()'''.

Уменьшить искажения отчасти помогает применение в качестве контейнеров текстурных изображений. Статистические характеристики текстур позволяют оптимизировать соотношение между количеством встраиваемых данных и качеством визуального восприятия. Пример текстурного контейнера при встраивании данных в четыре битовые плоскости всех RGB-компонент показан на рис. 3.

{{Врезка|Содержание=[[Изображение:LXF136_66_1.jpg|300px|Рис. 3]] Рис. 3. Пример текстурного контейнера со встроенными данными в четыре битовые плоскости всех RGB-компонент.|Ширина=300px}}

Объем встраиваемых данных в примере на рис. 3 приблизительно составляет '''Q = 1,18 МБ'''. Объем исходного изображения-контейнера равен 2,4 МБ. Коэффициент использования равен около 49 %.

Как можно судить из названия способа, для встраивания данных без потерь необходимо использовать графические BITMAP-форматы типа BMP, TIFF и т. п. С этим связан основной недостаток данного способа, обусловленный значительным объемом файлов изображений в формате BITMAP. Если этот фактор окажется существенным, то можно воспользоваться структурным способом, представленным ниже.

===Структурный способ===

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

Рассмотрим программную реализацию структурного встраивания на примере формата JPEG. Деление на сегменты в этом случае осуществляется с помощью маркеров, которые принято записывать в шестнадцатеричном виде '''0xFF 0xnn''', где шестнадцатеричное число '''nn''' указывает на то, какую функциональную нагрузку несет тот или иной сегмент. Любой маркер начинается байтом '''0xFF'''. Например, значения '''0xFF 0xD8''', расположенные в нулевом и первом байтах файла изображения, обозначают начало изображения (SOI) JPEG-формата. '''0xFF 0xD9''' соответствует признаку конца изображения (EOI). Далее представлен вариант программы для встраивания секретных данных в поле перед признаком начала информационного блока '''0xFF 0xС4''':

<source lang=perl>
open FIMG, “images/filein.jpg”;
binmode(FIMG );
@FILE_IMG=<FIMG>;
close FIMG;
$data=join(“”, @FILE_IMG);
@JPG = unpack(“C*”, $data);
$marker=”\xff\xc4”;
$pos =index($data, $marker);
$message=”секретное сообщение”;
@C1 = unpack(“C*”, $message);
@BEGIN=@JPG[0..$pos - 1];
@END=@JPG[$pos..scalar(@JPG)];
@UNIT=(@BEGIN,@C1,@END);
$out = pack(“C*”, @UNIT);
open JPEG, “>images/fileout.jpg”;
binmode(JPEG);
print JPEG $out;
close JPEG;
</source>

В приведенном примере встраивание данных осуществляется во внутренний сегмент файла формата JPEG, и поэтому программа должна отслеживать возможность появления байтов '''0xFF''', преобразовывать их или удалять. Можно реализовать более простой вариант программы, не требующий анализа байтов '''0xFF''', если производить встраивание данных в конец файла. Ниже представлен пример встраивания в файл архива в формате ZIP.

<source lang=perl>
open FILE, “$PATH/example.zip”;
binmode(FILE);
@FILE_ZIP=<FILE_ZIP>;
close FILE;
$zip=join(“”, @FILE_ZIP);
@ZIP = unpack(“C*”, $zip);
@UNIT=(@ZIP,0xff,0xd9);
$out = $data.pack(“C*”, @UNIT);
</source>

Завершающими байтами встроенных данных будет признак конца файла: '''0xFF 0xD9'''. Отметим, что объем встраиваемых данных при использовании структурного способа может быть произвольным и значительно превышать размер файла изображения-контейнера, и не создавать при этом никаких визуальных искажений. Недостатком рассмотренного подхода будет предсказуемость мест для встраивания скрываемых данных. Применение облачных web-технологий позволяет устранить этот недостаток, если мы разобьем скрываемые данные на '''N''' частей, встроим их в '''N*L''' изображений-контейнеров и разместим на '''L''' HTTP-серверах в Интернете. С учетом развития современных web-технологий реализовать подобное совсем не сложно.

===Голографический подход===

{{Врезка|Содержание=[[Изображение:LXF136_66_2.jpg|400px|Рис. 4]] Рис. 4. Встраивание образца подписи: а) контейнер со встроенной голограммой, б) результат восстановления водяного знака.|Ширина=400px}}

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

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

Формула для встраивания цифровых голограмм '''h(x,y)''' в изображение-контейнер '''g(x,y)''' имеет вид:

s(x,y) = g(x,y) + h(x,y),

где '''s(x,y)''' – результирующее изображение со встроенной голограммой водяного знака '''W(u,v)'''. Получение голограммы осуществляется с помощью обратного преобразования Фурье

h(x,y) = F-1{W1(u,v)}, (1)

где F-1 – оператор обратного преобразования Фурье, '''W1(u,v) = W(u-m,v-N) + W(-u-m,-v-N)''' – сумма изображений водяного знака и его зеркального отражения, '''m''' и '''N''' – смещение относительно начала координат в частотной плоскости '''u,v'''. Параметры '''m''' и '''N''' являются ключами голограммы. Рассмотрим фрагмент кода для вычисления голограммы:

<source lang=perl>
for($y=0;$y<$NN; $y++){
for($x=0;$x<$NN; $x++){
$wx[$x][$y]=0;
$wy[$x][$y]=0;
}}
for($y=0;$y<$Yh; $y++){
for($x=0;$x<$Xw; $x++){
$wx[$x+$M][$y+$N] = $W[$x][$y];
$wx[$NN $x $M 1][$NN $y $N 1] = $W[$x][$y];
}}
&d2cdfti(\@wx,\@wy,\$NN,\$PI);
for($y=0;$y<$NN; $y++){
for($x=0;$x<$NN; $x++){
$h[$x][$y]=$wx[$x][$y];
}}
</source>

Двумерное обратное преобразование Фурье выполняется с помощью подпрограммы '''d2cdfti()''', код которой был представлен в предыдущей статье этого цикла. Размер квадратной матрицы изображения контейнера '''g(x,y)''' задается параметром '''$NN''', а размеры массива '''@W''' водяного знака '''W(u,v)''' задаются переменными '''$Yh''' и '''$Xw'''. Параметры смещения '''$N''' и '''$M''' не должны превышать половины '''$NN''' за вычетом '''$Yh''' и '''$Xw''', соответственно.

Основной недостаток этого способа связан с ограниченным объемом встраиваемых данных. Наиболее целесообразно применять голографический подход для сокрытия небольших изображений, восстановление которых допускает некоторую потерю качества (подобно JPEG): образцов подписей, отпечатков пальцев, номера и серии паспорта и т. п. На рис. 4а представлено изображение-контейнер в формате JPEG со встроенным факсимильным образчиком подписи. Качество JPEG-изображения наивысшее – 100 %. На рис. 4б показан результат восстановления образца подписи; параметры смещения '''N''' и '''m''' составляли 118 и 120 пикселей, соответственно. Вариант для сокрытия дактилоскопического отпечатка иллюстрируется на рис. 5а. Двоичное изображение водяного знака встраивалось во все три RGB-компоненты. Качество JPEG-изображения было средним и равнялось 50 %, а сжатие по сравнению со 100 % качеством составило 75 %. На рис. 5б представлен результат восстановления образца отпечатка с параметрами смещения '''N''' и '''m''' равными 199 и 204 пикселей, соответственно.

{{Врезка|Содержание=[[Изображение:LXF136_67_1.jpg|400px|Рис. 5]] Рис. 5. Встраивание образца отпечатка пальца: а) контейнер со встроенной голограммой, б) результат восстановления водяного знака.|Ширина=400px}}

На рис. 4б и рис. 5б восстановленные образцы водяных знаков имеют зеркальное отображение, что обусловлено появлением мнимого изображения при восстановлении голограммы Фурье. Процесс восстановления голограммы является процедурой, обратной встраиванию водяных знаков, и поэтому, в соответствии с формулой (1), потребуется выполнить прямое преобразование Фурье изображения-контейнера. Отметим, что для обнаружения и восстановления секретных данных требуется априорное знание параметров '''N''' и '''m''', при которых создавалась голограмма.

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

{{Врезка|Содержание=[[Изображение:LXF136_67_2.jpg|300px|Рис. 6]] Рис. 6. Блок-схема процесса идентификации владельца кредитной карты.|Ширина=300px}}

Фотоизображение на рис. 6 считывается с помощью сканера на ПЗС-матрице, подвергается преобразованиям с целью восстановления скрытого водяного знака, и затем скрытая информация выводится на дисплей. На схеме, скрытые данные представляют собой графическое изображение знака копирайта ©.

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

LXF137:Perl

2014-04-22T08:49:17Z

Mike2014: ссылка на автора

: '''Распознавание образов''' Напишем программу, которая читает номерные знаки автомобилей

==Perl: Обнаружим объекты==

{{Цикл/Perl}}[[Категория:Учебники]][[Категория:Perl]]

: '''Часть 4''': Реализация объектов в ''Perl'' оставляет желать лучшего, но это не значит, что с его помощью нельзя находить объекты на фотографиях, считает [http://www.smirnov.sp.ru/ '''Михаил Смирнов'''].

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

{{Врезка|Содержание=[[Изображение:LXF137_73_1.jpg|Рис. 1|300px]] Рис. 1. Фотографическая карта местности: а) полутоновое входное изображение; б) контурное представление.|Ширина=300px}}

Ярким примером служат системы навигации и наведения крылатых ракет по рельефу местности. В качестве эталонов используются карты местности, изображения которых предварительно заносятся в память бортового компьютера. В ходе полета видеосистема ракеты сканирует местность, а компьютер оценивает корреляцию текущего изображения местности с набором эталонов и корректирует положение ракеты в пространстве относительно расчетной траектории полета. В систему наведения крылатой ракеты входит электронно-оптическая корреляционная подсистема, которая выдает результаты в реальном времени. Цифровые картины-эталоны предварительно отснятых районов местности последовательно вводятся в электронно-оптический коррелятор по мере перемещения ракеты вдоль траектории полета. Бортовой компьютер оценивает величины корреляции и прокладывает курс ракеты по рельефу местности. Нужно отметить, что в соответствии со свойствами зрительного восприятия для улучшения результатов сравнения применяется корреляция по контурам рельефа местности. На рис. 1 представлен пример фотографической карты местности и её контурное (градиентное) представление. Контурное представление может быть получено с помощью, например, дифференциального оператора Собеля или с помощью высокочастотной фильтрации видеоданных.

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

===Обнаружение, различение, опознавание===

Джонсон [J. Johnson], исследуя влияние видеосистем на восприятие военных объектов, установил три основных уровня видения, характеризующих процесс отождествления изображений данных объектов: обнаружение (появление объекта в поле зрения), различение (разбиение на классы: танки, автомобили) и опознавание типа объекта (например, наблюдается танк t-72). На рис. 2 иллюстрируется критерий Джонсона, где слева показаны периоды строчной развертки телевизионной системы наблюдения, а справа – контурное изображение автомобиля. Таким образом, Джонсон установил, что число полупериодов развертки, приходящихся на минимальный размер объекта, должно быть равно 2 (+1/-0.5) для обнаружения (рис. 2а), 8 (+1.6/-0.4) для классификации (рис. 2б) и 12.8 (+3.2/-2.8) для опознавания (рис. 2в).

{{Врезка|Содержание=[[Изображение:LXF137_73_2.jpg|Рис. 2|300px]] Рис. 2. Иллюстрации к критерию Джонсона: а) уровень обнаружения объектов; б) уровень классификации объектов; в) уровень опознавания типа объекта.|Ширина=300px}}

Следовательно, если мы установим, что в изображении имеются танки и автомашины, то мы решим задачу обнаружения. Если нам удастся отделить изображения танков от изображений автомобилей, то мы решим задачу классификации. И, наконец, если мы сможем сказать, что танк на изображении является российским т-72, а не американским M1A2, мы решим задачу опознавания типа.

===Значимость контуров===

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

H(u,v) = u2 + v2,

где ''u, v'' – пространственные частоты. Действие данного фильтра как раз и представлено на рис. 1а. Программную реализацию градиентного фильтра мы рассмотрим чуть ниже, совместно с выполнением процедуры сравнения с эталоном, которая получила название согласованной фильтрации.

===Согласованная фильтрация===

Согласованный фильтр был впервые использован для обнаружения сигналов в радиолокации. В одной из предыдущих статей цикла ([[LXF135:Perl|LXF135]]) мы рассмотрели процедуру фильтрации для повышения качества фотоизображения. Для этого мы сформировали фильтр ''H(u,v)'' и умножили его на спектр фотоизображения ''S(u,v)''. На формальном уровне, с позиции теории линейной фильтрации, как фильтр для повышения качества, так и фильтр для согласованной фильтрации равноценны. Основное отличие согласованного фильтра состоит в том, что его импульсная характеристика ''h(x,y)'' должна быть согласована и сопряжена с функцией объекта ''s(x,y)'':

h(x,y) = s(x0-x, y0-y). (1)

Будем перемещать отклик ''h(x,y)'' относительно объекта и вычислять корреляцию между двумя этими функциями. Очевидно, что максимум корреляции будет достигнут в момент их совмещения. Такая процедура получила название свертки двух функций. Функция согласованного фильтра рассчитывается как преобразование Фурье функции отклика (1):

H(u,v) = S*(u,v)exp{-j(u·x0 + v·y0)}, (2)

где ''S(u,v)'' – спектр эталона (1), ''j'' – мнимая единица, а знак '''*''' обозначает комплексное сопряжение. Как мы видим, функция согласованного фильтра является комплексной, и поэтому в программной реализации мы должны предусмотреть перемножение комплексных чисел. Ниже представлен программный код, реализующий согласованную фильтрацию с помощью градиентного согласованного фильтра. Входное изображение предварительно заносится в двумерный массив '''@re'''. Размерность входного изображения равна '''N × N''' точек и определяется в программе параметром '''$N''', а размерность эталона ''s(x,y)'' задается параметрами '''$sx''' по ширине и '''$sy''' по высоте.

<source lang=perl>
for($j=0;$j<$N; $j++){
for($i=0;$i<$N; $i++){
$im[$i][$j] = 0;
$re1[$i][$j] = 0;
$im1[$i][$j] = 0;
}}
&d2cdft( \@re,\@im,\$N,\$PI );
for($j=0;$j<$sy; $j++){
for($i=0;$i<$sx; $i++){
$re1[$i][$j] = $s[$i][$j];
}}
&d2cdft( \@re1,\@im1,\$N,\$PI );
$N2 = int($N/2);
for($j=0;$j<$N; $j++){
$u = $j;
if($j > $N2) { $u = $j - $N;}
for($i=0;$i<$N; $i++){
$v = $i;
if($i > $N2) { $v = $i - $N;}
$gr = ($u**2 + $v**2)/$N;
$Ure = $gr*( $re[$i][$j]*$re1[$i][$j] + $im[$i][$j]*$im1[$i][$j] );
$im = $gr*( $im[$i][$j]*$re1[$i][$j] - $re[$i][$j]*$im1[$i][$j] );
$re[$i][$j] = $Ure;
$im[$i][$j] = $im;
}}
</source>

После преобразования Фурье входного изображения '''@re''' элементы массива '''$re[$i][$j]''' и '''$im[$i][$j]''' будут представлять собой вещественную и мнимую части спектра исходного изображения. Преобразование Фурье осуществляется с помощью подпрограммы '''d2cdft()''' быстрого преобразования Фурье, описание которой было дано в предыдущих статьях цикла ([[LXF135:Perl|LXF135]]).

Комплексные элементы массивов '''$re1[$i][$j]''' и '''$im1[$i][$j]''' согласованного фильтра также получены с помощью подпрограммы '''d2cdft()''', которая применяется к функции эталона. Перемножение элементов массива спектра исходного изображения и элементов согласованного фильтра осуществляется по правилу умножения двух комплексных чисел. Результат перемножения комплексных чисел умножается на значения функции градиентного фильтра '''$gr''', вычисляемой в каждой точке спектра как суммы квадратов пространственных частот (трансформант) '''$u''' и '''$v'''.

Чтобы получить результирующие корреляционные отклики, необходимо выполнить обратное преобразование Фурье с помощью подпрограммы '''d2cdfti()''' в соответствии с программным кодом:

{{Врезка|Содержание=[[Изображение:LXF137_74_1.jpg|Рис. 3|300px]] Рис. 3. Обнаружение символов цифры 3: а) исходное изображение; б) результат согласованной фильтрации с двоичным эталоном цифры 3; в) сечение корреляционного поля.|Ширина=300px}}

<source lang=perl>
&d2cdfti( \@re,\@im,\$N,\$PI );
$max = 0;
for($j=0;$j<$N; $j++){
for($i=0;$i<$N; $i++){
if( $re[$i][$j] > $max){ $max = abs($re[$i][$j]);}
}}
for($j=0;$j<$N; $j++){
for($i=0;$i<$N; $i++){
$out[$i][$j] = abs(255*($re[$i][$j]/$max));
}}
</source>

Двумерные массивы '''@re''' и '''@im''', на входе подпрограммы '''d2cdfti()''', являются результатом умножения спектра входного изображения на согласованный фильтр, как это было показано в предыдущем фрагменте кода. На выходе подпрограммы '''d2cdfti()''' двумерный массив '''@re''' будет представлять собой результат корреляции эталона с входным изображением. Выходное корреляционное поле записывается в массив '''@out''', элементы которого '''$out[$i][$j]''' нормируются к максимальному значению '''$max''' и представляются в виде чисел от 0 до 255. В качестве примера рассмотрим обнаружение символов на номерных знаках автомобилей. На рис. 3 представлено исходное изображение и результаты обнаружения цифры 3 на номерном знаке автомашины с помощью согласованной градиентной фильтрации, программную реализацию которой мы рассмотрели. Эталоном для обнаружения служит двоичное изображение цифры 3.

Размерность исходного изображения на рис. 3а составляет '''1024 × 1024''' отсчетов. Размерность эталона равна '''sx=19''' отсчетам по ширине и '''sy=40''' отсчетам по высоте. Отметим, что пики максимумов корреляции будут смещены относительно объектов на половину размеров эталона, то есть на величину '''sx/2''' по ширине и '''sy/2''' по высоте.

Сделаем акцент на одном важном моменте согласованной фильтрации. Фильтр (2) является пространственно-инвариантным, или, иначе говоря, его действие справедливо для всего входного изображения. Это вытекает из формулы (1) для свертки, в которой операция свертки входного изображения ''s(x,y)'' с откликом ''h(x,y)'' осуществляется по всей плоскости при перемещении эталона вдоль осей ''x0‑x'' и y0‑y. По этой причине согласованный фильтр обеспечит обнаружение сразу нескольких (множества) объектов, расположенных произвольным образом во входном изображении.

===Водяные знаки===

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

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

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

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

{{Врезка|Содержание=[[Изображение:LXF137_75_1.jpg|Рис. 4|300px]] Рис. 4. Фотоизображение со встроенными видимыми знаками ©.|Ширина=300px}}

<source lang=perl>
$op = .075;
$dh0 = 64;
$dw0 = 64;
$dh = 128;
$dw = 128;
$L = $N/128;
for($h=0;$h<$L; $h++){
$m = $h*$dh + $dh0;
for($w=0;$w<$L; $w++){
$n = $w*$dw + $dw0;
for($j=0;$j<$sy;$j++){
for($i=0;$i<$sx;$i++){
$sum = $re[$i+$n][$j+$m] + $op*$re1[$i][$j];
if($sum > 255){ $sum = 255;}
$re[$i+$n][$j+$m]=$sum;
}}
}}
</source>

Входное и выходное изображения помещаются в двумерный массив '''@re'''. Параметр '''$op''' определяет непрозрачность водяного знака относительно исходного фотоизображения и равен в данном случае '''7,5 %'''. Параметры '''$dh0''' и '''$dw0''' дают начальные смещения (отступы) по высоте и ширине фотоизображения, соответственно. Значения параметров '''$dh''' и '''$dw''' задают шаг встраивания водяных знаков по высоте и ширине снимка. Параметр '''$L''' определяет число встраиваемых меток как по высоте, так и по ширине фотоизображения. С помощью параметров '''$sy''' и '''$sx''' задаются размеры встраиваемого знака '''©''', а так же размеры эталона '''©''' на этапе обнаружения. Значение '''255''' служит ограничителем на случай возможного превышения значения яркости. На рис. 4 представлен результат встраивания прозрачного знака '''©'''. Водяные знаки равномерно размещены по полю изображения, образуя матрицу, имеющую восемь рядов и восемь столбцов.

{{Врезка|Содержание=[[Изображение:LXF137_75_2.jpg|Рис. 5|300px]] Рис. 5. Результаты обнаружения знаков '''©''' с помощью согласованной фильтрации: а) поле корреляции; б) одно из сечений поля корреляции.|Ширина=300px}}

На рис. 5 представлены результаты обнаружения искомых символов '''©'''. В качестве эталона использовалось двоичное изображение знака '''©'''.

Анализ полученных результатов позволяет нам сделать вывод, что при прозрачности водяных знаков, равной '''92,5 %''', ошибки обнаружения (ошибки I рода) отсутствуют, а также отсутствуют ошибки ложного обнаружения, то есть II рода. Если мы будет увеличивать прозрачность водяных знаков, тем самым уменьшая их видимость, то неминуемо появятся ошибки ложного обнаружения, а затем и ошибки I рода. Уровень возникновения ошибок зависит от конкретного входного изображения. Для фотоизображения на рис. 4 ошибки II рода начинают появляться при величине прозрачности водяных знаков, равной 95 %, а ошибки I рода – при 97 %.

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

LXF135:Perl

2014-04-22T08:47:28Z

Mike2014: ссылка на автора

: '''''Math::FFT''' Perl'' и математические преобразования «вытянут» безнадежные с виду снимки

==''Perl'': Повысим качество фото==

{{Цикл/Perl}} [[Категория:Учебники]]

: '''Часть 2''': Большинство, наверное, возьмет для этих целей графический редактор, но [http://www.smirnov.sp.ru/ '''Михаил Смирнов'''] проделает все сам, с помощью ''Perl'' и изрядной доли математики.

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

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

===Немного теории===

{{Врезка|Содержание=[[Изображение:LXF135_68_1.jpg|300px|Рис. 1]] Рис. 1. Функция передачи модуляции камеры на ПЗС.|Ширина=300px}}

Передаточная характеристика устройства на ПЗС – сканера, цифрового фотоаппарата или видеокамеры – полностью описывается функцией передачи модуляции (ФПМ), которая характеризует падение контраста синусоидальных составляющих сигнала изображения в области пространственных частот. При оценке передаточной характеристики этих устройств одновременно будет учитываться и ФПМ оптического объектива, который фокусирует изображение в плоскости чипа ПЗС. В оптике пространственные частоты определяются как число линий на миллиметр, то есть величиной [1/мм]. В качестве примера на рис. 1 представлена типичная кривая ФПМ камеры на ПЗС.

ФПМ характеризует связь между исходным объектом и его изображением. Рассмотрим в качестве объекта синусоидальное распределение контраста, показанное на рис. 2а. Частота синусоиды равна 20 1/мм, то есть на одном миллиметре укладывается 20 периодов синусоиды.

На рис. 2б и 2в представлены сечения синусоидального объекта. Размах синусоиды на рис. 2б характеризует контраст объекта на входе устройства. На выходе оптико-электронного устройства изображение синусоиды будет характеризоваться сечением, показанным на рис. 2в. Таким образом, видно, что ФПМ на частоте 20 1/мм показывает падение сигнала синусоиды с величины 1.0 на входе устройства до величины примерно 0.18 на его выходе.

{{Врезка|Содержание=[[Изображение:LXF135_69_1.jpg|300px|Рис. 2]] Рис. 2. Пример синтеза изображения.

[[Изображение:LXF135_69_2.jpg|300px|Рис. 3]] Рис. 3. Край полуплоскости: а) тестовое изображение края полуплоскости, б) сечение края полуплоскости, в) функция рассеяния линии, г) ФПМ устройства на ПЗС, д) дефокусировочная кривая.|Ширина=300px}}

Для получения значений ФПМ на всех пространственных частотах потребуется множество синусоидальных объектов с различными частотами. Однако в этом нет необходимости, если воспользоваться объектом в виде протяженного резкого скачка контраста, получившего название «края полуплоскости». Изображение края полуплоскости показано на рис. 3а. Чтобы получить искомую ФПМ, необходимо выполнить дифференцирование края полуплоскости (по нормали к краю), а затем сделать преобразование Фурье.

Последовательность и результаты преобразований иллюстрируются на рис. 3. На рис. 3б показано одно из сечений края полуплоскости. Чтобы снизить влияние шумов ПЗС, перед дифференцированием предварительно выполняется усреднение сечений края полуплоскости. Суммирование m сечений края полуплоскости обеспечивает повышение отношения сигнал-шум в корень из ''m'' раз. Результат дифференцирования усредненного сечения края полуплоскости показан на рис. 3в – полученное нами распределение называется функцией рассеяния линии. Для определения ФПМ остается выполнить преобразование Фурье функции рассеяния и затем вычислить модуль от полученных комплексных коэффициентов Фурье (рис. 3г). Чтобы оценить ошибку, которую вносит цифровая оптико-электронная система, потребуется выполнить вычитание полученной нами ФПМ ''H(v)'' из так называемой дифракционной ФПМ ''Ĥ(v)'', которая имеет максимально достижимую частоту ''vm'':

U(v) = Ĥ(v) – H(v)

''v'' – пространственная частота. Предельная частота дифракционной ФПМ определяется простой формулой ''vm = F/λD'', где ''F'' – фокусное расстояние объектива; ''D'' – диаметр объектива; ''λ'' – длина волны света, обычно принимается равной 660 нанометрам (оранжевый цвет).

Дифракционная ФПМ (красная линия на рис. 3г) представляет собой наклонную прямую, равную 1 на нулевой частоте ''v = 0'' и равную 0 на дифракционной частоте ''vm''. Пример разностной
ФПМ ''U(v)'' показан на рис. 3д. Кривая на рис. 3д характеризует величину ошибки передачи контраста, которая обусловлена реальной оптико-электронной системой на ПЗС. Во многих случаях подобная ошибка связана с расфокусировкой объектива (потерей резкости). И действительно, распределение на рис. 3д напоминает дефокусировочную кривую.

Различные варианты настройки фокуса объектива будут, в той или иной степени, приводить к потере резкости. Чем сильнее расстроен объектив, тем больше будут значения разностной функции
''U(v)'' и тем хуже оптическое разрешение. При этом по пику кривой можно оценить пространственную частоту ''v'', на которой ФПМ имеет наибольший градиент падения контраста. Если не при-нимать в расчет шумы камеры на ПЗС, то наибольшее разрешение оптико-электронной системы определяется соотношением ''vL=1/2L'', где ''L'' – линейный размер ячейки ПЗС. Для реальных систем уровень шума на высоких частотах будет превышать сигнал изображения, и реальное предельное разрешение ''vr'' будет значительно ниже ''vL''.

Пример кода для получения искомой ФПМ показан ниже. Исходная матрица изображения '''B(x,y)''' края полуплоскости содержится в двумерном массиве '''@B'''. Начальная и конечная строки суммирования задаются параметрами '''$row1''' и '''$row2''', соответственно.

<source lang=perl>
for($j=$row1;$j<$row2; $j++){
for($i=0;$i<$N; $i++){
$g[$i] +=$B[$i][$j];
}}
$Nrr=$row2-$row1-1;
@g=map($_/$Nrr, @g);
for($i=1;$i<$N; $i++){
$PSF[$i] = $g[$i] - $g[$i-1];
}
use Math::FFT;
for($i=0;$i<$N;$i++){
$data->[2*$i]=$PSF[$i];
$data->[2*$i+1]=0;
}
$fft = new Math::FFT($data);
$coeff = $fft->cdft();
for($i=0;$i<$N;$i++){
$H[$i] = sqrt ( $coeff->[2*$i]**2 + $coeff->[2*$i+1]**2 );
}
@H=map($_/$H[0], @H);
</source>

Результат дифференцирования заносится в массив '''@PSF''', который представляет собой функцию рассеяния линии. Для выполнения преобразования Фурье воспользуемся математической библио
текой ''Perl'' '''Math::FFT''', в которой реализован алгоритм быстрого преобразования. Одномерное преобразование Фурье в этой библиотеке выполняется с помощью подпрограммы '''cdft()'''.

Результат преобразования Фурье заносится в массив коэффициентов '''$coeff''', где коэффициенты с четным индексом соответствуют реальной части, а коэффициенты с нечетным индексом – мнимой части комплексного числа, соответственно. Результирующая ФПМ заносится в массив '''@H''', значения которого нормируются к первому значению массива '''$H[0]''', соответствующему постоянной составляющей изображения. Таким образом, '''$H[0]=1''', а все остальные значения ФПМ меньше единицы.

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

===Улучшение качества===

Вывод, полученный нами в предыдущем разделе, позволяет сформулировать подход для улучшения качества фотоизображений, а именно: компенсировать падение ФПМ на тех частотах, где оно выражается наиболее сильно, и приблизить тем самым ФПМ к дифракционному пределу. В цифровой обработке изображений такие восстанавливающие фильтры получили название обратных или инверсных. Математически это выражается достаточно просто, а именно: спектр исходного фотоизображения ''S(v)'' необходимо умножить на функцию, обратную ФПМ устройства на ПЗС, которую мы ранее восстановили из изображения края полуплоскости. В предположении, что мощность шума пренебрежимо мала, спектр восстановленного изображения равен отношению ''S1(v) = S(v)/H(v)'', то есть функция идеального фильтра ''Q(v) = 1/H(v)''. Принимая во внимание шумы, которые вносятся любой реальной системой, необходимо найти решение для ''Q(v)'' на тех частотах ''v > vr'', где шум превышает сигнал. Предельная частота ''vr'' оценивается как частота, на которой дисперсия (энергия) шума начинает превышать значения ФПМ. Один из вариантов оптимального фильтра имеет вид

{{Врезка|Содержание=[[Изображение:LXF135_70_1.jpg|300px|Рис. 4]] Рис. 4. Оптимальный линейный фильтр для улучшения фотоизображений.|Ширина=300px}}

Q(v)= [1 + H(vr)2]•H(v)/[H(vr)2 + H(v)2] (1)

На рис. 4 показан результат расчета фильтра по формуле (1). Инверсные оптимальные фильтры, использующие восстановленные ФПМ, обеспечивают повышение контрастности на тех пространственных частотах, на которых это падение обусловлено реальной оптико-электронной системой. Это основное отличие восстанавливающих фильтров от «слепых» фильтров высоких частот или операторов типа Собеля для подчеркивания границ, применяемых в распространенных программных пакетах.

Алгоритм улучшения качества фотоизображения с помощью инверсной фильтрации включает следующие этапы. На первом этапе осуществляется преобразование Фурье исходного фотоизображения ''B(x,y)'' и получение спектра ''S(vx,vy)''. На втором этапе формируется инверсный фильтр ''Q(vx,vy)'', значения которого умножаются на спектр ''S(vx,vy)''. На третьем этапе выполняется обратное преобразование Фурье произведения ''S1(vx,vy) = S(vx,vy)•Q(vx,vy)'', результатом которого будет являться восстановленное изображение ''B1(x,y)''.

Первый и третий этапы реализуются с помощью стандартных подпрограмм одномерного преобразования Фурье модуля ''Perl'' '''Math::FFT'''. Двумерное преобразование Фурье получается с помощью последовательного применения одномерного преобразования, например, к функции изображения ''B(x,y)'' сначала по строкам, а затем по столбцам матрицы. Отметим, что преобразованию подвергаются RGB-компоненты цветного изображения по отдельности. В наших примерах используется компонента '''Blue''' исходного RGB-изображения. Ключевым этапом преобразования является второй этап, обеспечивающий развертывание одномерной функции фильтра в двумерный массив и умножение значений фильтра на спектр исходного изображения. Фрагмент программной реализации такого алгоритма фильтрации представлен ниже:

<source lang=perl>
$N2=$N/2;
for($i=0;$i<$N2;$i++) {
$FILTER[$i] = (1.+ $MTF[$nf]**2)*$MTF[$i]/($MTF[$nf]**2 +
$MTF[$i]**2);
}
for($j=0;$j<$N; $j++){
for($i=0;$i<$N; $i++){
$w2[$i][$j]=0;
}}
&d2cdft(\@B,\@w2,\$N,\$PI);
for($k=0;$k<$N; $k++){
$k1=$k;
if($k > $N2) { $k1=$k-$N;}
$x=$k1**2;
for($j=0;$j<$N; $j++){
$j1=$j;
if($j > $N2) { $j1=$j-$N;}
$R = sqrt ( $x +$j1**2 );
$Q = &parv(\$R,\@Xc,\@FILTER,\$N2);
$Re[$k][$j] *=$Q;
$Im[$k][$j] *=$Q;
}}
&d2cdfti(\@Re,\@Im,\$N,\$PI);
</source>

Входное фотоизображение содержится в двумерном массиве '''@B'''. Прямое и обратное двумерное преобразование Фурье выполняются с помощью подпрограмм '''d2cdft()''' и '''d2cdfti()''', соответственно. Исходная функция ФПМ, полученная нами выше, находится в массиве '''@MTF'''. Функция фильтра, рассчитанная по формуле (1), заносится в одномерный массив '''@FILTER'''. Для получения двумерной функции фильтра ''Q(vx,vy)'' используется подпрограмма линейной интерполяции '''parv()''', которая обеспечивает вычисление промежуточных значений фильтра в плоскости пространственныхчастот ''(vx,vy)''. Параметр '''R''' является текущим радиусом, а вспомогательный массив '''@Xc''' представляет собой массив аргумента входной функции фильтра, и, в частности, может быть задан как безразмерная функция с единичным шагом:

for($j=0;$j<$N2; $j++){$Xc[$j]=$j;}

Выходные значения восстановленного спектра ''S1'' фотоизображения заносятся в массивы реальной '''@Re''' и мнимой '''@Im''' части комплексного спектра ''S1'', соответственно. Результирующее восстановленное изображение, после выполнения обратного преобразования Фурье с помощью подпрограммы '''d2cdfti()''', помещается в двумерный массив '''@Re'''. На рис. 5 показано исходное и восстановленное фотоизображения, полученные с помощью цифровой фотокамеры в стандартном режиме съемки.

{{Врезка|Содержание=[[Изображение:LXF135_71_1.jpg|400px|Рис. 5]] Рис. 5. Результат компенсации ФПМ фотокамеры для стандартного режима съемки: а) исходное фотоизображение (Blue), б) результат восстановления.

[[Изображение:LXF135_71_2.jpg|400px|Рис. 6]] Рис. 6. Результат компенсации ФПМ фотокамеры для режима съемки макро: а) исходное фотоизображение (Blue), б) результат восстановления.|Ширина=400px}}

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

С точки зрения нагрузки на процессор, при выполнении процедур улучшения качества наиболее затратной является процедура интерполяции. Для уменьшения времени обработки фотоизображения можно заранее сформировать двумерную матрицу фильтра ''Q(vx,vy)'' и хранить его на диске. Для перемножения матриц спектра исходного фотоизображения ''S(vx,vy)'' и матрицы фильтра ''Q(vx,vy)'' можно воспользоваться пакетом (модулем) ''Perl'' '''PDL'''. Основное достоинство пакета '''PDL''' – высокая скорость сложения и перемножения матриц большой размерности и компактное хранение массивов данных с плавающей запятой. Например, скалярное произведение двух матриц вещественных чисел с плавающей запятой и размерностью 2048 × 2048 составляет около 1 секунды, а сложение таких матриц займет доли секунды. Двумерный массив чисел с плавающей запятой размерностью 1024 × 1024, принимая тип данных '''PDL''', будет занимать всего 4 МБ оперативной памяти. Пакет '''PDL''' позволяет лаконично записывать математические операторы для работы с матрицами в виде одной строки – например, код для скалярного умножения двух матриц '''$a''' и '''$b''' будет иметь вид

<source lang=perl>
use PDL;
$c = $a * $b;
</source>

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

<source lang=perl>
$re = pdl[@Re];
$im = pdl[@Im];
$q = pdl[@Q];
$re = $q*$re;
$im = $q*$im;
</source>

Уважаемый читатель, если вас поначалу озадачили «преобразование Фурье» и реализация математических формул, то отнеситесь к ним как к «черному ящику». Главная польза применения '''Math::FFT''' для оценки качества состоит в том, что с помощью небольшой программы на ''Perl'' у вас появилась возможность объективно сравнивать оптическое разрешение современных фото- и видеосистем во всей полосе видеочастот, а не ориентироваться только на один параметр разрешения – количество мегапикселей.

LXF134:Perl

2014-04-18T08:42:38Z

Mike2014:

: '''''GD и Perl''''' Создайте динамические изображения в ваших сценариях для Web, и не только

==''Perl'': Создаем изображения==

{{Цикл/Perl}}

: '''Часть 1''': Язык, созданный для обработки текстов, может неплохо справляться и с графикой. [http://www.smirnov.sp.ru/ '''Михаил Смирнов'''] объяснит, что к чему.

Как известно, язык программирования ''Perl'' идеально приспособлен для многочисленных приложений по обработке текста. Однако возможности ''Perl'' этим не исчерпываются. Применение графических модулей в ''Perl'' позволит вам быстро рисовать изображения, состоящие из линий, окружностей и текста, манипулировать цветом, вырезать и вставлять другие изображения, выполнять заливку, сохранять на диске файлы изображений в различных форматах, манипулировать видеоданными этих файлов. Наибольший интерес представляет использование графических модулей ''Perl'' в web-приложениях. Графическая библиотека ''GD'' имеет интуитивно понятный интерфейс, позволяющий быстро и компактно реализовать пользовательский код программ на ''Perl'' даже начинающим программистам.

Эффективность использования графического модуля ''GD'' объясняется просто: библиотека ''GD'' написана на языке ''C'' и совместима со всеми основными платформами (Linux, Windows, ...). Интерфейс между ''Perl'' и библиотекой ''GD'' обеспечивает модуль ''GD.pm'', который использует ''GD'' как базис для создания графических классов в ''Perl. GD.pm'' является самозагружаемым интерфейсным модулем, с помощью которого можно создавать изображения на лету, модифицировать существующие файлы изображений и синтезировать новые.

===Привет, ''GD''!===

Библиотека ''GD'' позволяет создавать цветные рисунки, используя большое количество графических примитивов, и выводить их в различных графических форматах. Модуль ''GD'' определяет три основных класса:
* класс изображений '''GD::Image''', который предназначен для захвата видеоданных изображения и выполняет вызов методов графических примитивов;
* класс шрифтов '''GD::Font''', который берет статические шрифты и использует их для воспроизведения текста в графическом виде;
* класс примитивов полигона '''GD::Polygon''', применяемый для сохранения списка вершин многоугольников при рисовании сторон полигона и обеспечивающий их воспроизведение в виде изображения.

Обобщенный подход использования графического интерфейса ''GD'' выглядит следующим образом. На первом этапе, при вызове (инициализации) метода '''GD::Image::new(Wx,Hy)''', создается новое пустое изображение, ширина и высота которого задаются параметрами '''Wx''' и '''Hy'''. В результате вызова метода будут возвращены видеоданные изображения. Другие методы класса позволяют инициализировать изображение из уже существующих файлов, которые необходимо предварительно прочитать с диска.

На втором этапе, при вызове метода '''colorAllocate()''' выполняется добавление цвета к цветовой таблице изображения. Входными параметрами вызова является тройка основных цветов: красный, зеленый и синий, которые задаются целыми числами в диапазоне значений от 0 до 255. Метод возвращает индекс цвета цветовой таблицы изображения.

{{Врезка|Содержание=[[Изображение:LXF134_76_1.jpg|300px|Рис. 1.]] Рис. 1. Пример рисования простых объектов.|Ширина=300px}}

После этого, на третьем этапе, можно сделать некоторый рисунок, используя набор графических примитивов класса '''GD::Image''' и набор методов класса '''GD::Polygon'''. Полигоны (многоугольники) создаются с помощью метода '''new()''', а добавление новых вершин полигона возложено на метод '''addPt()'''.

И, наконец, когда рисунок готов, вы можете преобразовать его, например, в графический формат GIF, с помощью метода '''gif()'''. Метод будет возвращать двоичное содержимое изображения в формате GIF. Обычно полученный результат выводится в браузер или сохраняется на диске в виде GIF-файла. В качестве примера приведем скрипт, который рисует простые фигуры, манипулирует ими самими и их цветом, а также рисует текст с помощью статических шрифтов:

<source lang=perl>
#!/perl/bin/perl
use GD;
$im = new GD::Image(425,250); #--Инициализация изображения
$black = $im->colorAllocate(0, 0, 0); #--Создаем цветовую палитру
$red = $im->colorAllocate(255, 0, 0);
$blue = $im->colorAllocate(0,0,255);
$yellow = $im->colorAllocate(255,250,0);
$bg = $im->colorAllocate(240,240,240);
$gray = $im->colorAllocate(128,128,128);
$im->fill(0,0,$bg); #--Делаем заливку фона
$im->rectangle(0,0,424,249,$black); #--Рисуем границы изображения
$poly = new GD::Polygon; #--Инициализация полигона
$poly->addPt(5,50);
$poly->addPt(25,25);
$poly->addPt(100,50);
$poly->addPt(70,95);
$poly->addPt(30,100);
$im->filledPolygon($poly,$blue); #--Создание полигона
$poly->offset(100,100); #--Смещение полигона
$im->polygon($poly,$red); #--Рисуем только контур
$poly->map($poly->bounds,190,10,390,150); #--Изменение масштаба полигона в 2 раза
$im->filledPolygon($poly,$yellow);
$im->arc(180,50,95,75,0,360,$blue); #--Рисуем эллипсы и дуги
$im->arc(280,190,90,50,290,180,$blue);
$im->arc(380,190,50,90,0,360,$blue);
$im->fill(380,190,$red);
$im->filledRectangle(10, 130, 50, 240, $gray); #--Рисуем четырехугольник
$im->rectangle(10,130,50,240,$black);
$string=”LINUX FORMAT”;
$im->string(gdMediumBoldFont,260,25,$string,$blue); #--Задаем статические шрифты
$im->string(gdSmallFont,170,235,”Copyright 2010”,$black);
print “Content-Type: image/gif\n\n”;
binmode STDOUT;
print $im->gif(); #--Преобразование данных в формат GIF и вывод
</source>

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

===Основные методы===

В иерархии интерфейсов ''GD'' наибольшее распространение получили два типа версий для работы с растровой графикой. Первый тип поддерживает манипулирование и преобразование изображений в формате GIF. Второй тип интерфейсов ''GD'' позволяет работать с такими популярными графическими форматами, как PNG и JPEG.

Для закрепления полученных выше практических навыков рассмотрим несколько «теоретических» моментов инициализации основных методов ''GD''. Вызов метода '''GD::Image::new(Wx,Hy)''' возвращает новое пустое изображение, например:

<source lang=perl>
$myImage = new GD::Image(100,100) || die;
</source>

Метод создает пустой бланк изображения размером 100 × 100 точек. Если размер опущен, он будет составлять 64 × 64 точек. Метод '''GD::Image::newFromGif(FILE)''' создает изображение на основе данных файла в формате GIF, предварительно прочитанного с диска. Параметр '''FILE''' представляет собой указатель файла (дескриптор). Дескриптор файла указывается как один из параметров функции '''open()'''. Если открытие файла было успешным, то вызов возвращает инициализированное изображение, которое затем может быть подвергнуто различным манипуляциям. Например:

<source lang=perl>
open (MyGIF,”images/ballon.gif”) || die;
$myImage = newFromGif GD::Image(MyGIF) || die;
close MyGIF;
</source>

'''MyGIF''' здесь – указатель файла. Вызов метода '''GD::Image::gif''' возвращает видеоданные изображения в формате GIF. Затем их можно вывести в браузер и/или записать в файл. Например:

<source lang=perl>
open (MyGIF,”>images/ballon.gif”);
binmode(MyGIF);
print MyGIF $im->gif;
close (MyGIF);
print “Content-Type: image/gif\n\n”;
binmode STDOUT;
print $im->gif;
</source>

Метод '''GD::Image::colorAllocate(R,G,B)''' предназначен для задания и управления цветом с помощью RGB-спецификации – цветовых компонент R (красный), G (зеленый) и B (синий), и в результате возвращает индекс цветовой таблицы. Пример задания желтого цвета:

<source lang=perl>
$yellow = $myImage->colorAllocate(255,255,0);
</source>

Полученные индексы впоследствии можно использовать для задания общего фона изображения или для заливки фигур определенным цветом. Метод '''GD::Image::getPixel(x,y)''' возвращает индекс цветовой таблицы под определенной точкой изображения с координатами (x,y). Вызов этого метода может быть скомбинирован с функцией '''rgb()''', если вам потребуется восстановить список RGB-компонент под выбранной точкой. Например:

<source lang=perl>
$index = $myImage->getPixel(20,100);
($r,$g,$b) = $myImage->rgb($index);
</source>

Метод '''GD::Image::transparent(colorIndex)''' отмечает индекс '''colorIndex''' как прозрачный. Участки изображения, нарисованные этим цветом, будут невидимы. Метод применяется для создания прозрачных фонов изображений в Web. Прозрачным в изображении может быть только один цвет. Ниже, например, им будет белый:

<source lang=perl>
open(myGIF,”transptest.gif”);
$im = newFromGif GD::Image(myGIF);
$white = $im->colorClosest(255,255,255);
$im->transparent($white);
print $im->gif;
close myGIF;
</source>

===Команды рисования===

Эти команды хотя и не занимают в иерархии методов ''GD'' особого положения, но выделяются своей выраженной функциональностью. Интуитивная простота команд (методов) позволит вам быстро нарисовать целый ряд примитивов или запрограммировать произвольный рисунок. Рассмотрим ряд наиболее употребляемых методов.

Метод '''GD::Image::setPixel(x,y,color)''' создает точку с координатами (x,y) с определенным цветовым индексом '''color'''. Он ничего не возвращает. Система координат начинается в верхнем левом углу и заканчивается в нижнем правом. Нетрудно представить, что растровый перебор координат при наличии функциональной зависимости цветового индекса '''color'' от координат (x,y) может использоваться для синтеза изображений. Реализуем пример кода для формирования двумерного распределения функции '''w=sin(x,y)''':

{{Врезка|Содержание=[[Изображение:LXF134_77_1.jpg|300px|Рис. 2.]] Рис. 2. Пример синтеза изображения.|Ширина=300px}}

<source lang=perl>
$im = new GD::Image($X,$Y);
$arg=$period*4*$pi*$pi;
for($j=0;$j<$Y; $j++){
$y = ($j-$Y/2)/$Y;
$phy = $y*$y;
for($i=0;$i<$X; $i++){
$x = ($i-$X/2)/$X;
$phx = $x*$x;
$w = int($a0 + $amp*sin($arg*($pi - $phx - $phy)));
$gray = $im->colorResolve($w,$w,$w);
$im->setPixel($i,$j,$gray);
}}
</source>

Метод '''colorResolve(r,g,b)''' возвращает индекс цвета, который точно соответствует указанным красным, зеленым и синим компонентам. Если такой цвет не находится в цветной таблице, то метод добавляет цвет в таблицу и возвращает его индекс. На рис. 2 представлен результат синтеза изображения, созданного в соответствии свыше приведенным кодом.

Метод '''GD::Image::rectangle(x1,y1,x2,y2,color)''' рисует четырехугольник, стороны которого имеют определенный цвет '''color'''. Координаты (x1,y1) и (x2,y2) являются верхним левым и правым нижним углами, соответственно. Пример рисования квадрата размером 90 × 90 точек:

<source lang=perl>
$myImage->rectangle(10,10,100,100,$blue);
</source>

Метод '''GD::Image::polygon(polygon,color)''' рисует многоугольник с заданным цветом '''color''', при этом число вершин не должно быть менее трех. Если последняя вершина полигона не создана, метод будет закрыт. Пример рисования треугольника:

<source lang=perl>
$poly = new GD::Polygon;
$poly->addPt(50,0);
$poly->addPt(99,99);
$poly->addPt(0,99);
$myImage->polygon($poly,$blue);
</source>

Метод '''GD::Image::line(x1,y1,x2,y2,color)''' рисует линию с определенным цветом '''color''' от точки с координатами (x1,y1) до точки с координатами (x2,y2). Пример рисования диагональной синей линии от точки с координатами (7,7) до точки с координатами (154,154):

<source lang=perl>
$myImage->line(7,7,154,154,$blue);
</source>

Метод рисования '''line()''' очень часто применяется для построения графиков функции одной переменной. Фрагмент кода скрипта, реализующий основной цикл формирования линии графика, а также оси абсцисс и значений переменной по оси абсцисс, представлен ниже:

{{Врезка|Содержание=[[Изображение:LXF134_78_1.jpg|300px|Рис. 3.]] Рис. 3. Пример построения графика функции одной переменной.|Ширина=300px}}

<source lang=perl>
$f=0;
for($i=0;$i<$N-1;$i++){
$im->line($x,$y[$i],$x+$dx,$y[$i+1],$blue);
$im->line($x,$yh,$x+$dx,$yh,$black);
$im->string(gdTinyFont, $x, $yh+2, $f, $blue);
$f +=5;
$x=$x+$dx;
}
</source>

Пример рисования графика функции одной переменной показан на рис. 3.

С помощью метода '''GD::Image::arc(cx,cy,Wx,Hy,start,end,color)''' можно рисовать дуги и эллипсы. Координаты (cx,cy) являются центром эллипса (дуги), а параметры (Wx,Hy) являются шириной и высотой эллипса, соответственно. Часть эллипса покрывается дугой, длина которой управляется параметрами '''start''' и '''end'''. Эти параметры задаются в угловой мере от 0 до 360 градусов. Пример рисования полного эллипса:

<source lang=perl>
$myImage->arc(100,100,50,35,0,360,$blue);
</source>

Метод '''GD::Image::fill(x,y,color)''' служит для заливки областей изображения с заданным цветом '''color'''. Цвет будет распространяться по изображению, начиная от точки (x,y) до границ объекта,
на которых появляется разностный цвет. Пример заливки синим цветом, начиная с точки с координатами x=50 и y=40:

<source lang=perl>
$myImage->rectangle(10,10,100,100,$black);
$myImage->fill(50,40,$blue);
</source>

===Копирование===

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

Метод '''GD::Image::copy(sourceImage,dstX,dstY,srcX,srcY,Wx,Hy)''' предназначен для копирования прямоугольных областей от одного изображения к другому. Изображение-источник задается с помощью параметра '''sourceImage'''. Параметры (srcX,srcY) задают верхний левый угол прямоугольника в изображении-источнике, а (Wx, Hy) указывают ширину и высоту области копирования. Параметры (dstX,dstY) управляют координатами точки, в которой будет начинаться наложение копии на изображение-получатель. Вызов метода возвращает данные изображения-получателя. Пример копирования области '''$srcImage''' размером 25 × 25 точек в область '''$myImage''' с началом в точке (10,10) показан ниже:

<source lang=perl>
$myImage = new GD::Image(100,100);
$srcImage = new GD::Image(50,50);
$myImage->copy($srcImage,10,10,0,0,25,25);
</source>

С изобразительной точки зрения, более интересным методом является метод '''GD::Image::copyMerge(sourceImage,dstX,dstY,srcX,srcY,Wx,Hy,opaque)''', который отличается от предыдущего всего лишь одним параметром '''opaque'''. Он может пригодиться для создания коллажей. С помощью параметра opaque в диапазоне значений от 0 до 100 задается степень прозрачности одного изображения относительно другого, например:

{{Врезка|Содержание=[[Изображение:LXF134_79_1.jpg|300px|Рис. 4.]] Рис. 4. Пример слияния двух изображений с эффектом прозрачности.|Ширина=300px}}

<source lang=perl>
$image1->copyMerge($image2,$left,$top,0,0,$wx,$hy, 60);
</source>

На рис. 4 показан пример слияния с эффектом прозрачности двух изображений одного размера. При этом прозрачность второго изображения относительно первого составляет 60 %.

===Выводим текст===

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

Интерфейс ''GD'' поддерживает минимальный набор статических шрифтов и позволяет рисовать символы и строки текста в графическом виде. Вывод может выполняться как в горизонтальном направлении, так и в вертикальном. Доступными для рисования шрифтами являются следующие: TinyFont, SmallFont, MediumBoldFont, LargeFont и GiantFont. Каждый из этих шрифтов может быть импортирован как глобальная константа или как пакет объектов класса '''GD::Font''', например: '''GD::Font::gdTinyFont'''.

Непосредственно для рисования применяется два основных метода: '''string()''' и '''stringUp()'''. Метод '''string(font,x,y,string,color)''' рисует строку текста, начиная с позиции (x,y), в заданном цвете и выбранном шрифте. Метод '''stringUp(font,x,y,string,color)''' рисует текст с поворотом на 90 градусов в направлении, противоположном вращению часовой стрелки.

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

Использование динамических шрифтов TrueType обеспечивает при рисовании текста практически неограниченные возможности, и прежде всего, локализацию под любой тип кодировки, применяемый в web-программировании. Метод для вызова шрифтов имеет вид '''GD::Image->stringTTF()'''. Разнообразие же существующих шрифтов снимает ограничения на их доступность. Один из вариантов вызова метода '''stringTTF()''' имеет вид:

{{Врезка|Содержание=[[Изображение:LXF134_79_2.jpg|300px|Рис. 5.]] Рис. 5. Пример рисования текста динамическими шрифтами.|Ширина=300px}}

<source lang=perl>
$image->stringTTF($fgcolor,$fontname,$ptsize,$angle,$x,$y,$str),
</source>

где аргументы команды – это:
* индекс цвета '''fgcolor''' для рисования строки текста,
* путь '''fontname''' к выбранному файлу шрифта (.ttf),
* желаемый размер '''ptsize''' шрифта,
* угол поворота '''angle''' в радианах,
* декартовы координаты x,y начала рисования,
* строка текста '''str'''.

На рис. 5 показан результат рисования строки текста несколькими кириллическими шрифтами: buaril.ttf, bukursv.ttf, buroman.ttf, butimit.ttf, pushkin.ttf, butimes.ttf.

===Форматы PNG и JPEG===

Как было отмечено выше, второй тип интерфейсов ''GD'' предоставляет возможность использовать графические форматы PNG и JPEG. Для работы с графическим форматом PNG применяется метод '''GD::Image->newFromPng($file)''', который с помощью дескриптора файла может создавать изображения в этом формате. Если открытие файла было успешным, то вызов возвращает инициализированное изображение, например:

<source lang=perl>
open (myPNG,”test.png”) || die;
$myImage = newFromPng GD::Image(\*myPNG) || die;
close myPNG;
print “Content-type: image/png\n\n”;
binmode STDOUT;
print $im->png();
</source>

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

<source lang=perl>
$myImage = newFromPng GD::Image('test.png')
</source>

Для работы с форматом JPEG применяется метод '''GD::Image->newFromJpeg($file)'''. Этот метод будет создавать изображение в формате JPEG после чтения файла с диска в том же формате:

<source lang=perl>
$quality=75;
$image = GD::Image->newFromJpeg($file);
print “Content-type: image/jpeg\n\n”;
binmode STDOUT;
print $image->jpeg($quality);
</source>

Отличительная особенность метода '''jpeg()''' – наличие параметра качества '''$quality''', задаваемого как целое в диапазоне значений от 0 до 100. Чем больше его значение, тем выше качество изображения, и, естественно, больше размер файла на диске. Если он не задан, по умолчанию будет выбрано среднее качество.