Обзор и реализация сжатия изображений с использованием алгоритма кластеризации k-средних и сравнение сжатых изображений для различных значений k
Сжатие изображений - это тип сжатия данных, применяемый к цифровым изображениям без снижения качества изображения до неприемлемого уровня. Уменьшение размера файла позволяет хранить больше изображений на заданном объеме диска или в памяти. Это также сокращает время, необходимое для отправки изображений через Интернет или загрузки с веб-страниц.
Как работает сжатие изображений? [1]
Алгоритмы сжатия изображений I используют преимущества визуального восприятия и статистические свойства данных изображения для обеспечения превосходных результатов. Есть два типа методов сжатия изображений - без потерь и с потерями. Давайте быстро взглянем на них обоих.
Сжатие без потерь:
Этот метод используется для уменьшения размера файла при сохранении того же качества, что и до его сжатия. Сжатие без потерь не ухудшает качество данных, и файл может быть восстановлен в его первоначальной форме. Размер файла при этом типе сжатия не меняется. Для сжатия без потерь используются следующие алгоритмы:
- Кодировка длины прогона
- Кодирование Хаффмана
- Арифметическое кодирование
Сжатие с потерями.
Сжатие с потерями - это метод сжатия, который удаляет незаметные данные. Чтобы придать фотографии еще меньший размер, сжатие с потерями отбрасывает некоторые менее важные части фотографии. Сжатый файл невозможно восстановить в его первоначальном виде. В этом типе сжатия данных ухудшается качество и изменяется размер данных. Сжатие с потерями используется в основном для изображений, аудио и видео, а также для различных алгоритмов сжатия с потерями:
- Дискретное косинусное преобразование
- Фрактальное сжатие
- Преобразование кодирования
Мы будем использовать метод кластеризации K-средних для сжатия изображений, который является разновидностью метода сжатия преобразования. Используя кластеризацию K-средних, мы выполним квантование цветов, присутствующих в изображении, что в дальнейшем поможет в сжатии изображения.
Что такое кластеризация K-средних?
Алгоритм K-средних - это метод кластеризации на основе центроидов. Этот метод группирует набор данных в k различных кластеров. Каждый кластер в алгоритме кластеризации k-средних представлен своей точкой центра тяжести.
На изображении выше (изображение 1) показано, как 3 кластера формируются для данного набора данных с использованием алгоритма кластеризации k-средних со значением k = 3.
Кроме того, прочтите эту статью, чтобы узнать больше об алгоритме кластеризации k-средних.
Как метод кластеризации K-средних сжимает изображение?
В цветном изображении каждый пиксель имеет размер 3 байта (RGB), где каждый цвет может иметь значения интенсивности от 0 до 255. Согласно комбинаторике общее количество цветов, которое может быть представлено, составляет 256 * 256 * 256 (равно 16 777 216 ). На практике мы можем визуализировать только несколько цветов в изображении, намного меньшем, чем указанное выше число. Таким образом, алгоритм кластеризации k-средних использует преимущество визуального восприятия человеческого глаза и использует небольшое количество цветов для представления изображения. Цвета с разными значениями интенсивности, которые являются значениями RGB, кажутся человеческому глазу одинаковыми. Алгоритм K-средних использует это преимущество и объединяет похожие цвета (которые находятся близко друг к другу в кластере). Вот иллюстрация того, как это работает:
На приведенном выше изображении (Изображение 2) несколько пикселей выбраны и увеличены в других изображениях, чтобы продолжить иллюстрацию.
Пиксели, выбранные на (Изображение 2) из входного изображения, расширены в левой части (Изображение 3). В правой части (Изображение 3) выбраны два соседних пикселя (названия «x» и «y»).
Если значение RGB для пикселей x и y равно (130, 131, 140) и (127, 132, 137) соответственно, то ниже приведена иллюстрация того, как эти двухпиксельные цвета видны человеческому глазу. Приведенная ниже иллюстрация интенсивности RGB к цвету подготовлена из w3schools.
На приведенном выше изображении (Изображение 4) видно, что для некоторого количества изменений значений RGB цвет напоминает то же самое, что и человеческий глаз. Таким образом, кластеризация k-средних может объединять эти два цвета вместе и может быть представлена точкой центра тяжести, которая имеет почти такое же сходство с человеческим глазом.
Исходный размер изображения 750 * 1000 пикселей. Для каждого пикселя изображение имеет 3 измерения, представляющие значения интенсивности RGB. Значения интенсивности RGB варьируются от 0 до 255. Поскольку значение интенсивности имеет 256 значений (2 ** 8), поэтому объем памяти, необходимый для хранения каждого значения пикселя, составляет 3 * 8 бит.
Наконец, начальный размер изображения составляет (750 * 1000 * 3 * 8) бит.
Общее количество цветовых комбинаций равно (256 * 256 * 256) (равно 16 777 216). Поскольку человеческий глаз не может воспринимать такое количество цветов одновременно, идея состоит в том, чтобы объединить похожие цвета вместе и использовать меньшее количество цветов для представления изображения.
Мы будем использовать кластеризацию k-средних, чтобы найти k цветов, которые будут представлять похожие цвета. Эти k-цвета будут точками центра тяжести алгоритма. Затем мы заменим каждое значение пикселя его центроидными точками. Комбинация цветов, сформированная с использованием только значений k, будет намного меньше по сравнению с общей комбинацией цветов. Мы попробуем разные значения k и посмотрим на выходное изображение.
Если k = 64, то окончательный размер выходного изображения будет (750 * 1000 * 6 + 64 * 3 * 8) бит, поскольку значение интенсивности колеблется до 2 ** 6.
Если k = 128, то окончательный размер выходного изображения будет (750 * 1000 * 7 + 128 * 3 * 8) бит, так как значение интенсивности изменяется до 2 ** 7.
Следовательно, наблюдается, что окончательный размер изображения в значительной степени уменьшается по сравнению с исходным изображением.
Реализация:
Пошаговое руководство по реализации:
- Ввод изображения (строки 6–8) : загрузите изображение с диска.
- Изменить форму входного изображения (строка 15) : Размер входного изображения (строки, столбцы, 3), сгладить все значения пикселей до одного измерения размера (строки * cols), а размер каждого пикселя равен 3, что соответствует значениям RGB. Размер сведенного изображения будет (строки * столбцы, 3).
- Кластеризация (строки 18–19) : Реализуйте алгоритм кластеризации k-средних, чтобы найти k-центроидные точки, которые представляют окружающую его цветовую комбинацию.
- Замените каждый пиксель его центроидными точками (строки 22–23) : Вся цветовая комбинация (строк * столбцов) количества пикселей теперь представлена его центральными точками. Замените значение каждого пикселя его точкой центра тяжести.
- Изменить форму сжатого изображения (строка 26) : изменить форму сжатого изображения (строк * столбцов, 3) размеров до исходных (строк, столбцов, 3) размеров.
- Выходное сжатое изображение (строки 29–31) : отображение выходного изображения и сохранение его на диск.
Результаты и наблюдения:
Исходное изображение:
Сжатые изображения для разных значений "k":
Приведенные выше 8 изображений описывают результат сжатых изображений для различных значений k.
Вот подробности обо всех входных и выходных изображениях:
Наблюдения на изображении выше:
- Размеры всех сжатых изображений (compressed_image_k.png) такие же, как у входных изображений (original_image.png).
- Размер сжатого изображения уменьшается с уменьшением k.
- Для значения k = 32, 64, 128, 256 сжатые изображения на выходе кажутся достаточно хорошими, теряют цвета и не видны человеческому глазу. Размер сжатого изображения уменьшается почти в 3 раза по сравнению с исходным изображением для k = 32.
- Для значения k = 16, 8 выходные сжатые изображения теряют много цветов, и сжатие с потерями становится видимым человеческому глазу.
- Для значения k = 4, 2 выходные сжатые изображения теряют почти все цвета, а также теряется содержимое изображения.
Ссылки:
[1] keycdn.com, (21 ноября 2018 г.), Что такое сжатие изображений? Htps: //www.keycdn.com/support/what-is-image-compression
Спасибо за чтение!
