From 7ac882e3a313d59b4a5478e1e0f0583f8ca473bd Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sat, 24 Dec 2022 23:20:10 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?= =?UTF-8?q?=20=D0=BB=D0=B5=D0=BA=D1=86=D0=B8=D1=8F=20=D0=BF=D0=BE=20=D1=81?= =?UTF-8?q?=D0=B6=D0=B0=D1=82=D0=B8=D1=8E?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- compression/presentation/images/YCbCr.jpg | Bin 0 -> 90675 bytes compression/presentation/images/compare.png | Bin 0 -> 119408 bytes compression/presentation/images/dct64.png | Bin 0 -> 299254 bytes compression/presentation/images/fractal.png | Bin 0 -> 131289 bytes compression/presentation/images/q1.png | Bin 0 -> 117120 bytes compression/presentation/images/q2.png | Bin 0 -> 414829 bytes compression/presentation/images/subd.png | Bin 0 -> 9236 bytes compression/presentation/maker.sh | 35 ++++ compression/presentation/presentation.tex | 254 ++++++++++++++++++++++++++++ 9 files changed, 289 insertions(+) create mode 100644 compression/presentation/images/YCbCr.jpg create mode 100644 compression/presentation/images/compare.png create mode 100644 compression/presentation/images/dct64.png create mode 100644 compression/presentation/images/fractal.png create mode 100644 compression/presentation/images/q1.png create mode 100644 compression/presentation/images/q2.png create mode 100644 compression/presentation/images/subd.png create mode 100755 compression/presentation/maker.sh create mode 100644 compression/presentation/presentation.tex (limited to 'compression/presentation') diff --git a/compression/presentation/images/YCbCr.jpg b/compression/presentation/images/YCbCr.jpg new file mode 100644 index 0000000..0e2e538 Binary files /dev/null and b/compression/presentation/images/YCbCr.jpg differ diff --git a/compression/presentation/images/compare.png b/compression/presentation/images/compare.png new file mode 100644 index 0000000..fa73e34 Binary files /dev/null and b/compression/presentation/images/compare.png differ diff --git a/compression/presentation/images/dct64.png b/compression/presentation/images/dct64.png new file mode 100644 index 0000000..af6d55d Binary files /dev/null and b/compression/presentation/images/dct64.png differ diff --git a/compression/presentation/images/fractal.png b/compression/presentation/images/fractal.png new file mode 100644 index 0000000..5800b44 Binary files /dev/null and b/compression/presentation/images/fractal.png differ diff --git a/compression/presentation/images/q1.png b/compression/presentation/images/q1.png new file mode 100644 index 0000000..21cf39f Binary files /dev/null and b/compression/presentation/images/q1.png differ diff --git a/compression/presentation/images/q2.png b/compression/presentation/images/q2.png new file mode 100644 index 0000000..ab1c91d Binary files /dev/null and b/compression/presentation/images/q2.png differ diff --git a/compression/presentation/images/subd.png b/compression/presentation/images/subd.png new file mode 100644 index 0000000..3fccc28 Binary files /dev/null and b/compression/presentation/images/subd.png differ diff --git a/compression/presentation/maker.sh b/compression/presentation/maker.sh new file mode 100755 index 0000000..e847acf --- /dev/null +++ b/compression/presentation/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -exec rm {} \; + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc +} + +help() { + echo "Использование:" + echo "./maker.sh watch .tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc .tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac diff --git a/compression/presentation/presentation.tex b/compression/presentation/presentation.tex new file mode 100644 index 0000000..c25e980 --- /dev/null +++ b/compression/presentation/presentation.tex @@ -0,0 +1,254 @@ +\documentclass{beamer} + +\usepackage[T2A]{fontenc} +\usepackage[utf8]{inputenc} +\usepackage[english,russian]{babel} +\usepackage{wrapfig} +\usepackage{graphicx} +\usepackage{multirow} +\graphicspath{ {./images/} } + +\usetheme{Madrid} + +\title{Алгоритмы сжатия изображений} +\author[А.~Ю.~Гущин \and Р.~И.~Стаин]{Андрей~Гущин \and Роман~Стаин} +\institute[СГУ]{Саратовский Государственный Университет} +\date{11 ноября 2022 г.} + +\begin{document} + +\maketitle + +\begin{frame}{Представление цифровых изображений} + \begin{figure}[H] + \includegraphics[width=0.9\textwidth]{compare} + \end{figure} +\end{frame} + +\begin{frame}{Алгоритмы сжатия без потерь} + Основными и самыми популярными алгоритмами сжатия без потерь являются: + \begin{itemize} + \item + \textbf{RLE} --- используется в форматах PCX --- в качестве основного метода + и в форматах BMP, TGA, TIFF в качестве одного из доступных. + \item \textbf{LZW} --- используется в формате GIF + \item \textbf{Deflate} --- используется в формате PNG + \end{itemize} +\end{frame} + +\begin{frame}{Run-Length Encoding (RLE)} + \begin{itemize} + \item \texttt{WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW} + \pause + \item \texttt{9W3B24W1B14W} + \end{itemize} +\end{frame} +\begin{frame}{Run-Length Encoding (RLE)} + \begin{itemize} + \item \texttt{ABCABCABCDDDFFFFFF} + \pause + \item \texttt{1A1B1C1A1B1C1A1B1C3D6F} + \pause + \item \texttt{-9ABCABCABC3D6F} + \end{itemize} +\end{frame} +\begin{frame}{Run-Length Encoding (RLE)} + \begin{itemize} + \item + \texttt{AAAAA{\dots}AAAAA} + \pause + \item \texttt{127A127A2A} + \end{itemize} +\end{frame} + +\begin{frame}{Lempel-Ziv-Welch (LZW) --- Кодирование} + \begin{table}[H] + \centering + \scriptsize + \begin{tabular}{|c|c|c|r|l|} + \hline + % Первая строка заголовка + \multirow{2}{*}{Символ} & + \multirow{2}{*}{Следующий} & + \multicolumn{2}{|c|}{Вывод} & + \multirow{2}{*}{Расширение словаря} \\ \cline{3-4} + % Вторая строка заголовка + && Код & \multicolumn{1}{|c|}{Биты} & \\ \hline + % Символ & Следующий & Код & Биты & Расширение словаря \\ + NULL & T & & & \\ \hline + T & O & 20 & \texttt{10100} & 27: TO \\ \hline + O & B & 15 & \texttt{101111} & 28: OB \\ \hline + B & E & 2 & \texttt{100010} & 29: BE \\ \hline + E & O & 5 & \texttt{100101} & 30: EO \\ \hline + O & R & 15 & \texttt{101111} & 31: OR \\ \hline + R & N & 18 & \texttt{110010} & 32: RN \\ \hline + N & O & 14 & \texttt{1001110} & 33: NO \\ \hline + O & T & 15 & \texttt{1001111} & 34: OT \\ \hline + T & T & 20 & \texttt{1010100} & 35: TT \\ \hline + TO & B & 27 & \texttt{1011011} & 36: TOB \\ \hline + BE & O & 29 & \texttt{1011101} & 37: BEO \\ \hline + OR & T & 31 & \texttt{1011111} & 38: ORT \\ \hline + TOB & E & 36 & \texttt{1100100} & 39: TOBE \\ \hline + EO & R & 30 & \texttt{1011110} & 40: EOR \\ \hline + RN & O & 32 & \texttt{1100000} & 41: RNO \\ \hline + OT & \# & 34 & \texttt{1100010} & \\ \hline + & & 0 & \texttt{000000} & \\ \hline + \end{tabular} + \end{table} +\end{frame} +\begin{frame}{Lempel-Ziv-Welch (LZW) --- Декодирование} + \begin{table}[H] + \centering + \scriptsize + \begin{tabular}{|r|c|c|l|l|} + \hline + % Первая строка заголовка + \multicolumn{2}{|c|}{Ввод} & + \multirow{2}{*}{Вывод} & + \multicolumn{2}{|c|}{Новая запись} \\ \cline{1-2} \cline{4-5} + % Вторая строка заголовка + \multicolumn{1}{|c|}{Биты} & + Код & & + \multicolumn{1}{|c|}{Полная} & + \multicolumn{1}{|c|}{Частичная} \\ \hline + % Биты & Код & Вывод & Полная & Частичная \\ + \texttt{10100} & 20 & T & & 27: T? \\ \hline + \texttt{01111} & 15 & O & 27: TO & 28: O? \\ \hline + \texttt{00010} & 2 & B & 28: OB & 29: B? \\ \hline + \texttt{00101} & 5 & E & 29: BE & 30: E? \\ \hline + \texttt{01111} & 15 & O & 30: EO & 31: O? \\ \hline + \texttt{10010} & 18 & R & 31: OR & 32: R? \\ \hline + \texttt{001110} & 14 & N & 32: RN & 33: N? \\ \hline + \texttt{001111} & 15 & O & 33: NO & 34: O? \\ \hline + \texttt{010100} & 20 & T & 34: OT & 35: T? \\ \hline + \texttt{011011} & 27 & TO & 35: TT & 36: TO? \\ \hline + \texttt{011101} & 29 & BE & 36: TOB & 37: BE? \\ \hline + \texttt{011111} & 31 & OR & 37: BEO & 38: OR? \\ \hline + \texttt{100100} & 36 & TOB & 38: ORT & 39: TOB? \\ \hline + \texttt{011110} & 30 & EO & 39: TOBE & 40: EO? \\ \hline + \texttt{100000} & 32 & RN & 40: EOR & 41: RN? \\ \hline + \texttt{100010} & 34 & OT & 41: RNO & 42: OT? \\ \hline + \texttt{000000} & 0 & \# & & \\ \hline + \end{tabular} + \end{table} +\end{frame} + +\begin{frame}{Алгоритмы сжатия с потерями} + Наиболее часто применяемые алгоритмы сжатия с потерями: + \begin{itemize} + \item + Дискретное косинусное преобразование "--- кодирование, основанное на + преобразованиях Фурье. + \item Вейвлет сжатие "--- сжатие за счёт отбрасывания низких амплитуд. + \item Квантование цветов "--- процесс уменьшения количества различных цветов. + \item + Прореживание (субдискретизация) компонентов цветности "--- усреднение или + уменьшение части информации о цветности изображения. + \item + Фрактальное сжатие "--- алгоритм сжатия изображений с потерями, основанный + на применении систем итерируемых функций к изображениям + \end{itemize} +\end{frame} + +\begin{frame}{Преобразование цветового пространства} + \begin{figure}[H] + \includegraphics[width=0.9\textwidth]{YCbCr} + \end{figure} + \begin{align*} + Y' &= K_R \cdot R' + (1 - K_R - K_B) \cdot G' + K_B \cdot B' \\ + C_B &= \frac{1}{2} \cdot \frac{B' - Y'}{1 - K_B} \\ + C_R &= \frac{1}{2} \cdot \frac{R' - Y'}{1 - K_R} \\ + \end{align*} +\end{frame} + +\begin{frame}{Прореживание (субдискретизация) компонентов цветности} + Есть несколько схем прореживания, которые применяются в зависимости от + требований к качеству изображения после его восстановления. Структура + дискретизации сигнала обозначается как соотношение между тремя частями X:a:b + (например, 4:2:2). + + \begin{figure}[H] + \includegraphics[width=0.9\textwidth]{subd} + \end{figure} +\end{frame} + +\begin{frame}{Дискретное косинусное преобразование} + \begin{minipage}[t]{0.48\linewidth} + \begin{figure}[H] + \includegraphics[width=\textwidth]{dct64} + \end{figure} + \end{minipage} + \hfill + \begin{minipage}[t]{0.48\linewidth} + \begin{align*} + RES &= DCT \cdot IMG \cdot DCT^T \\ + DCT &= + \sqrt{\frac{2}{N}} \cdot + \cos{\frac{(2j + 1) \cdot i \cdot \pi}{2 \cdot N}} \\ + N &= 8, 0 \leq i, j \leq 7 + \end{align*} + \end{minipage} +\end{frame} + +\begin{frame}{Дискретное косинусное преобразование} + До преобразования ДКП: + \begin{equation*} + \begin{pmatrix} + 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ + 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ + 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ + 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ + 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ + 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ + 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 \\ + 100 & 100 & 100 & 100 & 100 & 100 & 100 & 100 + \end{pmatrix} + \end{equation*} +\end{frame} + +\begin{frame}{Дискретное косинусное преобразование} + После преобразования ДКП: + \begin{equation*} + \begin{pmatrix} + 800 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ + 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ + 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ + 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ + 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ + 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ + 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ + 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 + \end{pmatrix} + \end{equation*} +\end{frame} + +\begin{frame}{Квантование и кодирование} + \begin{minipage}[t]{0.48\linewidth} + \begin{figure}[H] + \includegraphics[width=\textwidth]{q1} + \end{figure} + \end{minipage} + \hfill + \begin{minipage}[t]{0.48\linewidth} + \begin{figure}[H] + \includegraphics[width=\textwidth]{q2} + \end{figure} + \end{minipage} +\end{frame} + +\begin{frame}{Фрактальное сжатие изображений} + \begin{figure}[H] + \includegraphics[width=\textwidth]{fractal} + \end{figure} +\end{frame} + +\begin{frame} + \frametitle{Внимание!} + + \begin{center} + {\Huge Спасибо за внимание!} \\ + {\footnotesize Сжимайте осторожнее.} + \end{center} +\end{frame} + +\end{document} -- cgit v1.2.3