Палитра и доминантные цвета изображения

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

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

Палитра

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

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

Но сегодня все плохо по другому, скорее всего, мы уже не справимся с анализом палитры изображения вручную. А иногда все еще не имеет смысла хранить изображение представленного всеми исходными цветами, а сузить их количество до некоторого разумного предела. Так вот такой процесс называется квантизацией цвета: уменьшение количества цветов из всего подмножества, которым может быть представлено изображение до некоторого меньшего. Например, сильно утрируя процесс, 14bit raw цвет представить в 8bit jpeg или 16bit tiff сконвертировать в 8bit png и так далее.

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

Median cut

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

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

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

Локальные максимумы

Как ни странно, с локальными максимумами оказалось все прекрасно: нашелся код, который можно не только украсть творчески переработать, но и автор оказался прекрасным художником и в целом очень хорошо описал сам алгоритм. Суть реализации состоит в том, что сначала мы собираем статистику картинки в такую же  трехмерную RGB-гистограмму, как и в случае с алгоритмом Median Cut:

Каждая ячейка куба будет содержать бины цвета, и сумму всех значений каждого цвета входящего в ячейку. Поскольку размерность гистограммы ограничивается разрешением в 32x32x32 (что бы не плодить лишней сложности вычислений, и в оригинальном варианте 30x30x30), то накопление суммы упрощает расчет среднего цвета ячейки.

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

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

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

Реализация

На примере этой задачи покажу как просто, используя еще далеко неполный IMProcessing Framework, сварить готовое приложение для анализа и работы с изображением. Поскольку имплементировать уже существующую функциональность не так интересно, я начал с классов отсутствующих в других движках как класс. К примеру, фреймворк уже умеет читать файлы Adobe .cube с готовыми CLUT, а так же умеет в «режиме реального времени» извлекать 3-х мерную кубическую гистограмму из изображения. В предыдущем посте, я описал общую концепцию работы с фреймворком. Сегодня используя эти общие принципы сконструируем приложение, которое умеет:

1. Загружать файлы формата  JFIF (jpeg)
2. «Нормализовать» исходное изображение
3. Управлять степенью воздействия «нормализатора»
4. Добавлять к обработке произвольный LUT из файла Adobe формата .cube.
5. Управлять степенью воздействия CLUT
6. Показывать линейную гистограмму изображения
7. Показывать «сжатую палитру» и доминантные цвета изображения и их числовое представление в виде триплета (r,g,b)

В результате конструирования получим что-то вроде такой игрушки:

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

«Нормализатор»

Пока сильно чудить не будем и соберем фильтр из двух уже готовых:

1. IMPContrastFilter — позволяет растягивать гистограмму изображения до заданных границ

2. IMPAutoWBFilter — автокоррекция баланса белого основанная на поиске среднего цвета и коррекции паразитных тонов изображения. По сути это небольшая модификация идеи позаимствованной из блога Андрея Журавлева

import IMProcessing

/// Фильтр изображения
public class IMPTestFilter:IMPFilter {

    /// Будем использовать фильтр управления контрастом через растяжение гистограммы
    var contrastFilter:IMPContrastFilter!

    /// Фильтр автоматического баланса белого
    var awbFilter:IMPAutoWBFilter!

    /// Анализатор линейной гистограммы изображения
    var sourceAnalyzer:IMPHistogramAnalyzer!

    /// Солвер анализатора гистограммы расчета границ светлот изображения
    let rangeSolver = IMPHistogramRangeSolver()

    public required init(context: IMPContext) {
        super.init(context: context)

        //  Инициализируем фильтры в контексте
        contrastFilter = IMPContrastFilter(context: context)
        awbFilter = IMPAutoWBFilter(context: context)

        // Добавляем фильтры в стек
        addFilter(contrastFilter)
        addFilter(awbFilter)

        // Инициализируем анализатор гистограммы
        sourceAnalyzer = IMPHistogramAnalyzer(context: self.context)

        // добавляем к анализатору солвер поиска границ светлот
        sourceAnalyzer.addSolver(rangeSolver)

        // Добавляем к фильтру наблюдающий хендлер к фильтру для
        // для передачи текущего фрейма изображения анализатору
        addSourceObserver { (source) - Void in
            self.sourceAnalyzer.source = source
        }

        // Добавляем к анализатору наблюдающий хендлер обновления расчетов анализа
        sourceAnalyzer.addUpdateObserver({ (histogram) - Void in
            // устанавливаем при каждом изменении изображения границы светлот в контрастном фильтре
            self.contrastFilter.adjustment.minimum = self.rangeSolver.minimum
            self.contrastFilter.adjustment.maximum = self.rangeSolver.maximum
        })

    }
}

Солвер палитры

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

Для нашей цели: вычисления палитры и списка доминирующих цветов используем солвер для расширения анализа IMPHistogramCubeAnalyzer. Результаты вычислений будем отображать в обновляемом NSTableView.

import IMProcessing

///  Типы распределения цветовых акцентов изображения
///
///  - palette:   палитра квантирования цветов изображения.
///               расчитывается по сжеме median-cut преобрзования:
///               http://www.leptonica.com/papers/mediancut.pdf
///  - dominants: расчет доминантных цветов изображения через поиск локальных максимумов
///               функции плотности распределения цветов:
///               https://github.com/pixelogik/ColorCube
///
public enum IMPPaletteType{
    case palette
    case dominants
}

/// Солвер анализатора кубической гистограммы цветов IMPHistogramCubeAnalyzer
public class IMPPaletteSolver: IMPHistogramCubeSolver {

    /// Максимальное количество цветов палитры для анализа
    public var maxColors = Int(8)

    /// Список найденых цветов
    public var colors = [IMPColor]()

    /// Тип палитры
    public var type = IMPPaletteType.dominants

    ///  Хендлер обработчика солвера
    ///
    ///  - parameter analizer:  ссылка на анализатор
    ///  - parameter histogram: кубическая гистограмма изображния
    ///  - parameter imageSize: размер изображения
    public func analizerDidUpdate(analizer: IMPHistogramCubeAnalyzer, histogram: IMPHistogramCube, imageSize: CGSize) {

        var p = [float3]()
        if type == .palette{
            p = histogram.cube.palette(count: maxColors)
        }
        else if type == .dominants {
            p = histogram.cube.dominantColors(count: maxColors)
        }

        colors.removeAll()

        for c in p {
            colors.append(IMPColor(color: float4(rgb: c, a: 1)))
        }
    }
}

Спаиваем все в контроллере представления

В контроллере нам понадобятся основной фильтр приложения, назовем его оригинально: IMPTestFilter, фильтр CLUT: IMPLutFilter, готовый из коробки: IMPHistogramView — для отображения «обычной» гистограммы, IMPHistogramCubeAnalyzer — анализатор кубической гистограммы, к которому присоединим наш солвер IMPPaletteSolver. Наконец, IMPImageView — главное окно показа картинки и общий IMPContext — ключевой класс используемый всеми конструкторами фреймворка. 

class ViewController: NSViewController {

    //
    // Контекст процессинга
    //
    let context = IMPContext()
    //
    // Окно представления загруженной картинки
    //
    var imageView:IMPImageView!

    var pannelScrollView = NSScrollView()

    //
    // Окно вывода гистограммы изображения
    //
    var histogramView:IMPHistogramView!

    //
    // NSTableView - представления списка цветов из палитры
    //
    var paletteView:IMPPaletteListView!

    //
    // Основной фильтр
    //
    var filter:IMPTestFilter!

    //
    // Фильтр CLUT из фалов формата Adobe Cube
    //
    var lutFilter:IMPLutFilter?

    //
    // Анализатор кубической гистограммы изображения в RGB пространстве
    //
    var histograCube:IMPHistogramCubeAnalyzer!

    //
    // Наш солвер для поиска цветов
    //
    var paletteSolver = IMPPaletteSolver()

    var paletteTypeChooser:NSSegmentedControl!

    override func viewDidLoad() {

        super.viewDidLoad()

        configurePannel()

        //
        // Инициализируем кучу нужных нам объектов
        //

        filter = IMPTestFilter(context: context)

        histograCube = IMPHistogramCubeAnalyzer(context: context)
        histograCube.addSolver(paletteSolver)

        imageView = IMPImageView(context: context, frame: view.bounds)
        imageView.filter = filter
        imageView.backgroundColor = IMPColor(color: IMPPrefs.colors.background)

        //
        // Добавляем еще один хендлер к наблюдению за исходной картинкой
        // (еще один был доавлен в основном фильтре IMPTestFilter)
        //
        filter.addSourceObserver { (source) -> Void in
            //
            // для минимизации расчетов анализатор будет сжимать картинку до 1000px по широкой стороне
            //
            if let size = source.texture?.size {
                let scale = 1000/max(size.width,size.height)
                self.histograCube.downScaleFactor = scale.float
            }
        }

        //
        // Добавляем наблюдателя к фильтру для обработки результатов
        // фильтрования
        //
        filter.addDestinationObserver { (destination) -> Void in

            // передаем картинку показывателю кистограммы
            self.histogramView.source = destination

            // передаем результат в анализатор кубической гистограммы
            self.histograCube.source = destination
        }

        //
        // Результаты обновления расчета анализатора выводим в окне списка цветов
        //
        histograCube.addUpdateObserver { (histogram) -> Void in
            self.asyncChanges({ () -> Void in
                self.paletteView.colorList = self.paletteSolver.colors
            })
        }

        view.addSubview(imageView)

....

        IMPDocument.sharedInstance.addDocumentObserver { (file, type) -> Void in
            if type == .Image {
                do{
                    //
                    // Загружаем файл и связываем источником фильтра
                    //
                    self.imageView.source = try IMPImageProvider(context: self.imageView.context, file: file)
                    self.asyncChanges({ () -> Void in
                        self.zoomFit()
                    })
                }
                catch let error as NSError {
                    self.asyncChanges({ () -> Void in
                        let alert = NSAlert(error: error)
                        alert.runModal()
                    })
                }
            }
            else if type == .LUT {
                do {

                    //
                    // Инициализируем дескриптор CLUT
                    //
                    var description = IMPImageProvider.LutDescription()
                    //
                    // Загружаем CLUT
                    //
                    let lutProvider = try IMPImageProvider(context: self.context, cubeFile: file, description: &description)

                    if let lut = self.lutFilter{
                        //
                        // Если CLUT-фильтр добавлен - обновляем его LUT-таблицу из файла с полученным дескриптором
                        //
                        lut.update(lutProvider, description:description)
                    }
                    else{
                        //
                        // Создаем новый фильтр LUT
                        //
                        self.lutFilter = IMPLutFilter(context: self.context, lut: lutProvider, description: description)
                    }

                    //
                    // Добавляем LUT-фильтр, если этот фильтр уже был добавленб ничего не происходит
                    //
                    self.filter.addFilter(self.lutFilter!)
                }
                catch let error as NSError {
                    self.asyncChanges({ () -> Void in
                        let alert = NSAlert(error: error)
                        alert.runModal()
                    })
                }
            }
        }

   ....

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

Полностью проект можно забрать, собрать и опробовать из репозитория проекта ImageMetalling: ImageMetalling-08. Для правильной сборки локально должна быть установлена мега-библиотека для работы с файлами формата JPEG (JFIF) libjpeg-turbo.  На сегодняшний день это лучшая реализации поддержки этого формата.

Ссылка для скачивания приложения для тех кому даже собраться лень (совместима только с El Capitan и железом после середины 2012г.): ImageMetalling-08.app.

Писол! Всех с благополучно наступившим похмельем!

---

Авторы блога не преследуют задачи быть предельно корректным, но если заметили явную ашипку, если написали явную глупость, если что-то не понятно: комментируйте или пишите на: imagemetalling [*] gmail.com.

---

И да, никогда не используйте имплементацию этого формата NSImage/UIImage…