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

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

Формально сжатие изображений - это тип сжатия данных, применяемый к цифровым изображениям для снижения стоимости их хранения или передачи. Прежде чем перейти к реализации, давайте кратко рассмотрим алгоритм кластеризации K-средних. Кластеризация K-средних - это метод оптимизации для поиска k кластеров или групп в заданном наборе точек данных. Точки данных сгруппированы вместе на основе некоторого сходства. Первоначально он начинается со случайной инициализации кластеров k, а затем на основе некоторого сходства (например, метрики евклидова расстояния) стремится минимизировать расстояние от каждой точки данных до центра кластера в каждом кластере. В основном алгоритм состоит из двух итерационных шагов:

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

б) Шаг обновления - новые центры кластеров (центроиды) рассчитываются на основе точек данных, назначенных новому кластеру, путем выбора среднего значения этих точек данных.

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

К-средние, примененные к изображениям

В нашей проблеме сжатия изображения кластеризация K-средних группирует похожие цвета вместе в «k» кластеров (скажем, k = 64) разных цветов (значений RGB). Следовательно, каждый центроид кластера является представителем трехмерного цветового вектора в цветовом пространстве RGB его соответствующего кластера. Вы, наверное, уже догадались, насколько плавно можно применить метод K-средних к значениям пикселей, чтобы получить результирующее сжатое изображение. Теперь эти центроиды кластера «k» заменят все цветовые векторы в своих соответствующих кластерах. Таким образом, нам нужно только сохранить метку для каждого пикселя, которая сообщает кластеру, которому этот пиксель принадлежит. Кроме того, мы ведем учет цветовых векторов каждого центра кластера. Посмотрите на исходные и сжатые изображения ниже.

Теперь давайте посмотрим, действительно ли изображение сжато. Раньше каждый пиксель занимал 24 (8x3) бита для хранения соответствующего цветового вектора. После применения этого алгоритма для каждого пикселя требуется всего 6 бит, поскольку он хранит только метку кластера, которому он принадлежит (k = 64 в нашем примере). K = 64 различных цветовых вектора могут быть представлены с использованием только 6 бит. Таким образом, результирующее изображение будет иметь 64 разных цвета в цветовом пространстве RGB. Обратите внимание, что сжатие здесь будет с потерями, т.е. мелкие детали изображения могут исчезнуть после этого сжатия. Однако мы можем взять относительно большее значение «k», чтобы минимизировать эти потери и сделать их как можно меньше.

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

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

Спасибо за внимание!

Если вам понравилась эта статья, хлопайте, хлопайте, хлопайте… 👏 👏 👏