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



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


Гистограмма h полутонового изображения I задается выражением

$h(m)=|(r, c) | I(r, c)=m|$


, где m соответствует интервалам значений яркости

Ниже приведен псевдокод для вычисления гистограммы.


// Вычисление гистограммы H для полутонового изображения I.

procedure histogram(I,H);
{
    // Инициализация карманов гистограммы нулевыми значениями.
    for i := 0 to MaxVal
        H[i] := 0;

    // Накопительное вычисление значений.
    for L := 0 to MaxRow
        for P := 0 to MaxCol {
            grayval := I[r,c];
            H[grayval] := H[grayval] + 1;
        };
}

Визуально гистограмма представляет из себя прямоугольник, ширина которого равна максимально возможному значению яркости точки на исходном изображении. Для полутоновых изображений мы будем работать с диапазоном яркостей точек от 0 до 255, а значит и ширина гистограммы будет равна 256. Высота гистограммы может быть любой, но для наглядности мы будем работать с прямоугольными гистограммами.


С точки зрения программиста, гистограмма — это одномерный массив размерностью 256 (в нашем случае), где каждый элемент массива хранит в себе суммарное количество точек соответствующей яркостью. Ниже приведем визуальный пример подобной гистограммы.


Рисунок 1. Графическое отображение гистограммы h(x)



Здесь гистограмма отображена белым цветом. Синяя линия — это функция распределения cdf(x) и о ней мы поговорим чуть позже.


Как уже говорилось ранее, мы будем использовать библиотеку OpenCV для того, чтобы облегчить работу с окнами, загрузкой изображений и их обработкой. Известно, что библиотека уже содержит встроенную функцию для выравнивания гистограмм, тем интереснее будет сделать сравнение. Для работы с библиотекой из F# мы будем использовать порт OpenCVSharp4.


Здесь я не буду приводить инструкцию, как устанавливать этот порт в Visual Studio, этой информации много в интернете. Сделаю только одну ремарку, что для пользователей MacOS, после компиляции проекта, нужно вручную скопировать файл "runtimes/osx-x64/native/libOpenCvSharpExtern.dylib" в папку, где лежит ваш бинарный файл с программой. В противном случае при запуске программы будет возникать исключение
Unable to load shared library 'OpenCvSharpExtern' or one of its dependencies


Сразу реализуем функцию, которая будет вычислять гистограмму


open OpenCvSharp
open Microsoft.FSharp.NativeInterop

// mat - объект класса Mat библиотеки OpenCV
let getHistogram (mat: Mat) =
    // создаем пустую гистограмму
    let hx = Array.zeroCreate<int> 256
    // заполняем ее
    mat.ForEachAsByte(fun value _ ->
                           let v = int (NativePtr.get value 0)
                           hx.[v] <- hx.[v] + 1)
    // возвращаем гистограмму
    hx

Вернемся к функции распределения, упомянутой выше. Она определяется как сумма ячеек гистограммы от нуля до X


$cdx(x)=h(0)+h(1)+...+h(x)$


Функция распределения показывает, какое количество пикселей имеет яркости из отрезка от нуля до X. Пример функции распределения можно посмотреть на рисунке 1 (обозначена синим цветом).


Реализуем функцию, вычисляющую cdf(x)


let getCdx hx = // hx - гистограмма
   // возвращаем функцию распределения
   hx |> Array.mapi (fun x _ -> if x > 0 then hx.[0..(x-1)] |> Array.sum else 0)

Выравнивание гистограммы


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


Пример выровненной гистограммы можно увидеть на рисунке 2.


Рисунок 2. Выровненная гистограмма



Здесь видно, как выглядит гистограмма и функция распределения после применения алгоритма выравнивания гистограммы.


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


$f(x)=round(\frac{cdf(x)-cdf_{min}}{pixels-1}\cdot255)$


здесь
cdf(x) — Значение функции распределения для точки с яркостью X
cdf_min — Минимальное значение функции распределение, отличное от нуля
pixels — Общее количество пикселей в изображении
255 — максимально возможное значение яркости точки. Для полутоновых изображений это 255
round — функция округления полученного числа до целого значения


Реализуем фунцию F# для выравнивания гистограммы:


// получаем cdf_min
let cdxMin = cdx |> Array.filter (fun v -> v > 0) |> Array.min
// вычисляем суммарное количество точек в изображении
let totalPixels = src.Rows * src.Cols // src - объект типа Mat с загруженным изображением

for y in 0..src.Rows do
    for x in 0..src.Cols do
        // получаем яркость точки в изображении
        let s = int(src.At<byte>(y, x))
        // вычисляем новое значение по формуле
        let fx = (float(cdx.[s]) - float(cdxMin))/(float(totalPixels - 1))*255.
        // рисуем точку в изображении
        equalizeImage.Circle(x, y, 1, new Scalar(double(fx)))

Ниже приведем полный исходный код программы, которая берет исходное изображение и отображает ее гистограмму и функцию распределения. Также программа применяет функцию выравнивания гистограммы и показывает полученное изображение и ее гистограмму. И для сравнения, программа использует встроенную функцию OpenCV для выравнивания гистограммы и также показывает результат.


Выраванивание гистограмм
// Learn more about F# at http://fsharp.org
open OpenCvSharp
open Microsoft.FSharp.NativeInterop

// функция для вычисления гистограммы изображение
let getHistogram (mat: Mat) =
    let hx = Array.zeroCreate<int> 256
    mat.ForEachAsByte(fun value _ ->
                           let v = int (NativePtr.get value 0)
                           hx.[v] <- hx.[v] + 1)
    hx

// функция для вычисления функции распределения гистограммы
let getCdx hx =
    hx |> Array.mapi (fun x _ -> if x > 0 then hx.[0..(x-1)] |> Array.sum else 0)

// рисуем гистограмму и функцию распределения
let drawHistogramAndCdx hx cdx (mat: Mat) =
    let histoWidth = 256
    let histoHeight = 256

    // получаем максимальную величину функиции распределения
    let cdxMax = cdx |> Array.max
    // вычисляем поправочной коэффициент для сжатия (или растяжения)
    // функции распределения в гистограмме
    let cdxK = float(histoHeight)/float(cdxMax)

    let histMax = hx |> Array.max
    let histK = float(histoHeight)/float(histMax)

    let histMat = new Mat(histoWidth, histoHeight, MatType.CV_8UC4)
    hx
    |> Array.iteri (fun x v ->
                        let histDy = int(float(v)*histK)
                        let cdxDy = int(float(cdx.[x])*cdxK)
                        // рисуем гистограмму h(x)
                        mat.Line(x, histoHeight-1, x, histoHeight-1-histDy, Scalar.White)
                        // рисуем функцию распределения cdx(x)
                        mat.Circle(x, histoHeight-cdxDy, 1, Scalar.Blue))

[<EntryPoint>]
let main argv =

    let histoWidth = 256
    let histoHeight = 256

    let src = Cv2.ImRead("cat.jpg", ImreadModes.Grayscale)
    let equalizeImage = new Mat(src.Rows, src.Cols, MatType.CV_8UC1)

    // calculate histogram h(x)
    let hx = getHistogram src

    // calculate cdf(x) = h(0) + h(1) + .. + h(x)
    let cdx = getCdx hx

    // draw histogram
    let histMat = new Mat(histoWidth, histoHeight, MatType.CV_8UC4)
    drawHistogramAndCdx hx cdx histMat

    // equalize the histogram
    let cdxMin = cdx |> Array.filter (fun v -> v > 0) |> Array.min
    let totalPixels = src.Rows * src.Cols

    for y in 0..src.Rows do
        for x in 0..src.Cols do
            let s = int(src.At<byte>(y, x))
            let fx = (float(cdx.[s]) - float(cdxMin))/(float(totalPixels - 1))*255.
            //equalizeImage.Set<Scalar>(y, x, new Scalar(double(fx)))
            equalizeImage.Circle(x, y, 1, new Scalar(double(fx)))

    // calculate equalize histogram
    let hx2 = getHistogram equalizeImage
    let cdx2 = getCdx hx2

    let histMat2 = new Mat(histoWidth, histoHeight, MatType.CV_8UC4)
    drawHistogramAndCdx hx2 cdx2 histMat2

    // opencv equalize histogram
    let opencCVImage = new Mat(src.Rows, src.Cols, MatType.CV_8UC1)
    let in1 = InputArray.Create(src)
    let in2 = OutputArray.Create(opencCVImage)

    Cv2.EqualizeHist(in1, in2)

    // get opencv histogram
    let hx3 = getHistogram opencCVImage
    let cdx3 = getCdx hx3

    let histMat3 = new Mat(histoWidth, histoHeight, MatType.CV_8UC4)
    drawHistogramAndCdx hx3 cdx2 histMat3

    // show results
    use w1 = new Window("original image", src)
    use w2 = new Window("original histogram", histMat)

    use w3 = new Window("custom equalize image", equalizeImage)
    use w4 = new Window("custom equalize histogram", histMat2)

    use w5 = new Window("opencv equalize image", opencCVImage)
    use w6 = new Window("opencv equalize histogram", histMat3)

    Cv2.WaitKey() |> ignore

    0 // return an integer exit code

Сравниваем полученные результаты


Рисунок 3. Сравниваем результаты


Ниже приведены сравнительные примеры некоторых картинок, обработанных нашим алгоритмом и алгоритмом, встроенным в OpenCV.


Слева расположено исходное изображение (гистограмма ниже), посередине — изображение, обработанное нашим алгоритмом и справа — обработанное при помощи OpenCV.






Подводим итоги


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