Алгоритм сжатия изображений «вырезание швов»

Алгоритм Seam Carving (англ., примерно – «выдергивание нитей») используется, когда требуется масштабировать изображение, уменьшив его размер, но так, чтобы оно визуально оставалось цельным, не допустив деформации или обрезки важных элементов изображения.

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

Предобработка изображения

Определение яркости пикселей

👍 Пожалуйста, выполните подготовительный код (следующая ячейка) перед началом упражнения!

cd(@__DIR__);

using Images, ImageShow

Из выпадающего списка выберите имя файла для обработки IMG_001.jpg.

filename = "IMG_001.jpg" # @param ["IMG_001.jpg", "IMG_002.jpg", "IMG_003.jpg", "IMG_004.jpg", "IMG_005.jpg"]

I = load(filename)

Задание 1

Создайте функцию, которая поможет нам выделить наиболее яркие области изображения. Это нужно для определения границ объектов, находящихся на изображении.

Функция должна возвращать относительную яркость входного изображения (имеющего цветовые плоскости R, G и B), которая рассчитывается по формуле:

Применяя эту функцию к отдельным пикселям изображения, мы будем получать их яркость.

✏️ Задание: Дополните функцию brightness таким образом, чтобы она возвращала относительную яркость входного пикселя.

function brightness( pixel )
    return pixel.r + 0 + 0  # Впишите ваш код вместо этой строки
end

Подсказка

Воспользуйтесь свойствами pixel.r, pixel.g и pixel.b чтобы обратиться к разным цветовым составляющим пикселя.

Решение

function brightness(pixel)
    return 0.2126 * pixel.r + 0.7251 * pixel.g + 0.0722 * pixel.b
end

Задание 2

Чтобы проверить результат работы функции brightness на изображении, нужно применить ее к каждому пикселю.

✏️ Задание: Примените функцию brightness к изображению I, не забыв оператор . для поэлементного выполнения функции, чтобы применить ее к каждому пикселю изображения. Сохраните результат в переменной Ibright. Отобразите результат при помощи функции simshow.

Подсказка

Для применения функции ко всем элементам матрицы (изображения) требуется применять ее через . – brightness.(I).

Решение

Ibright = brightness.(I)
simshow(Ibright)

Обнаружение границ изображенных объектов

Задание 3

Обнаружение границ объектов в алгоритме Seam Carving реализуется при помощи фильтра sobel.

Данный фильтр может применяться для поиска либо вертикальных, либо горизонтальных границ.

engee> yFilter = Kernel.sobel()[1]

3×3 OffsetArray(::Matrix{Float64}, -1:1, -1:1) with eltype Float64 with indices -1:1×-1:1:
 -0.125  -0.25  -0.125
  0.0     0.0    0.0
  0.125   0.25   0.125

engee> xFilter = Kernel.sobel()[2]

3×3 OffsetArray(::Matrix{Float64}, -1:1, -1:1) with eltype Float64 with indices -1:1×-1:1:
 -0.125  0.0  0.125
 -0.25   0.0  0.25
 -0.125  0.0  0.125

Значимость пикселей изображения мы будем метафорично называть их энергией.

Чем больше энергия пикселя, тем более значимым он является. Пиксели с наименьшей энергией первыми вырезаются из изображения.

✏️ Задание: Дополните функцию find_energy, которая принимает на вход некоторое изображение image.

Используйте функцию imfilter, передав ей в качестве параметров изображение image, преобразованное при помощи функции brightness.(). Вторым аргументом передайте вариант фильтра sobel()[1]. Сохраните результат в energy_y.
Проделайте то же самое для переменной energy_x, используя вариант фильтра sobel()[2].

function find_energy( image )
    
    Ibright = [] # Введите ваш код вместо пустого массива "[]"
    yFilter = Kernel.sobel()[1]
    xFilter = Kernel.sobel()[2]

    energy_y = 0  # Введите ваш код вместо "0"
    energy_x = 0  # Введите ваш код вместо "0"
    
    return sqrt.(energy_x.^2 + energy_y.^2)
end

Подсказка

Найдите изображение Ibright = brightness.( image ) и примените к нему функции imfilter(Ibright, Kernel.sobel()[1]) и imfilter(Ibright, Kernel.sobel()[2]), сохранив результат в соответствующих переменных.

Решение

function find_energy(image)
    energy_y = imfilter(brightness.(image), Kernel.sobel()[1])
    energy_x = imfilter(brightness.(image), Kernel.sobel()[2])
    
    return sqrt.(energy_x.^2 + energy_y.^2)
end

Задание 4

✏️ Задание: Примените написанную вами функцию find_energy к изображению I, сохранив результат в переменной Ienergy. Отобразите Ienergy на экране.

Подсказка

Чтобы отобразить Ienergy, воспользуйтесь функцией simshow.

Решение

Ienergy = find_energy(I)
simshow(Ienergy)

Задание 5

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

Выполните следующую ячейку чтобы задать эту функцию:

function find_energy_map( energy )
    energy_map = zeros(size(energy));
    energy_map[end, :] = energy[end, :]
    
    next_elements = zeros(Int, size(energy));
    
    for i = size(energy)[1]-1:-1:1, j = 1:size(energy)[2]
        left = max(1, j-1)
        right = min(j+1, size(energy)[2])
        
        local_energy, next_element = findmin(energy_map[i+1, left:right])
        
        energy_map[i,j] = local_energy + energy[i,j]
        next_elements[i, j] = next_element - 2
        
        if left==1
            next_elements[i,j]+=1
        end
    end
    return energy_map, next_elements
end

Задание 6

Проверим работу функции find_energy_map. Результатом ее работы должно быть изображение, на котором светлые участки обозначают зоны, через которые не должен проходить «шов».

✏️ Задание: Вызовите функцию find_energy_map с аргументом Ienergy, присвоив результат ее работы переменным Ienergy_map и Inext_elements. Отобразите изображение Ienergy_map и проанализируйте полученный результат.

Подсказка

Присвойте аргументам energy_map, next_elements результат вызова функции find_energy_map(energy). Чтобы отобразить energy_map, воспользуйтесь функцией simshow.

Решение

Ienergy_map, Inext_elements = find_energy_map(Ienergy)
simshow(Ienergy_map)

Вырезание нитей

Определение положения нити

В этом разделе потребуется написать функции, которые будут определять положение шва и вырезать его из изображения.

Задание 7

Первая функция, которая нам потребуется, – find_seam_at. Она будет находить наилучший путь, по которому будет проходить шов, с началом в определенном пикселе.

Выполните следующую ячейку чтобы задать эту функцию:

function find_seam_at(next_elements, element)
    seam = zeros(Int, size(next_elements)[1])
    
    seam[1] = element
    
    for i=2:length(seam)
        seam[i] = seam[i-1] + next_elements[i, seam[i-1]]
    end
    
    return seam
end

Задание 8

Чтобы проверить работу функции find_seam_at, воспользуемся функцией draw_seam.
Задайте ее, выполнив следующую ячейку:

function draw_seam(image, seam)
    image_with_seam = copy(image)

    for i = 1:size(image)[1]
        image_with_seam[i, seam[i]] = RGB(1, 0, 1)
    end
    
    return image_with_seam
end

Для проверки выберем сотый пиксель изображения I.

✏️ Задание:

Поместите в переменную Iseam результат вызова функции find_seam_at с аргументами Inext_elements, 100.
Затем вызовите функцию draw_seam с аргументами I, Iseam.

Подсказка

Сперва нужно вызвать команду find_seam_at(Inext_elements, 100), присвоив результат ее выполнения переменной Iseam, а после вызвать функцию draw_seam(I, Iseam).

Решение

function draw_seam(image, seam)
    image_with_seam = copy(image)

    for i = 1:size(image)[1]
        image_with_seam[i, seam[i]] = RGB(1, 0, 1)
    end
    
    return image_with_seam
end

Iseam = find_seam_at(Inext_elements, 100)
I_with_seam = draw_seam(I, Iseam)

Задание 9

Теперь нужно создать функцию, которая будет автоматически определять наилучшее место для устраняемой нити пикселей. Этой функцией будет find_best_seam.

✏️ Задание: В теле функции find_best_seam:

Сперва вызовите функцию find_energy_map.
Присвойте результат ее выполнения переменным energy_map, next_elements.
Затем вызовите функцию findmin с аргументом energy_map[1, :] таким образом, чтобы она вернула индекс (номер) минимального элемента.
Присвойте полученное значение переменной min_element_number.

function find_best_seam(energy)
    energy_map, next_elements = find_energy_map(energy)
    min_element_number = findmin(energy_map[1, :])[2]
    
    return find_seam_at(next_elements, min_element_number)
end

Подсказка

Поскольку функция findmin возвращает 2 аргумента: значение и индекс минимального элемента массива, то для получения только номера минимального указывается индекс [2].

Решение

function find_best_seam(energy)
    energy_map, next_elements = find_energy_map(energy)
    min_element_number = findmin(energy_map[1, :])[2]
    
    return find_seam_at(next_elements, min_element_number)
end

Задание 10

Последняя функция для нашего алгоритма – remove_seam. Задайте ее, выполнив следующую ячейку:

function remove_seam(image, seam)
    image_new = image[:, 1:end-1]
    
    for i = 1:length(seam)
        if seam[i] > 1 && seam[i]< size(image)[2]
            image_new[i, :] .= vcat(image[i, 1:seam[i]-1], image[i, seam[i]+1:end])
            
        elseif seam[i]==1
            image_new[i, :] .= image[i, 2:end]
        elseif seam[i]==size(image)[2]
            image_new[i, :] .= image[i, 1:end-1]
        end
    end
    return image_new
end

Эта функция будет возвращать изображение, из которого удалена переданная ей в качестве аргумента нить пикселей. Убедимся, что она работает: вызовем ее и проверим размер полученного изображения при помощи функции size().
Изображение должно уменьшиться на один столбец пикселей.

✏️ Задание: При помощи функции size, убедитесь, что функция remove_seam работает. Примените ее сперва к изображению I, затем к Inew и сравните размеры полученного изображения с исходным.

Inew = [] # Впишите ваш код вместо пустого массива []

Isize = size( I )
Isize_new = size( Inew )

println( "Размер исходного изображения: ", Isize )
println( "Размер полученного изображения: ", Isize_new )

Подсказка

Поместите в переменную Inew результат вызова remove_seam с аргументами (I, Iseam).

Решение

Inew = remove_seam(I, Iseam)

Isize = size( I )
Isize_new = size( Inew )

println( "Размер исходного изображения: ", Isize )
println( "Размер полученного изображения: ", Isize_new )

Алгоритм Seam Carving в действии

Проверка работы алгоритма на примерах изображений

Функция image_carving реализует алгоритм Seam Carving.

Выполните следующую ячейку чтобы задать определение этой функции:

function image_carving( image, width )
    
    for i = ( 1:size(image,2)-width )
        energy = find_energy( image )
        seam = find_best_seam( energy )
        image = remove_seam( image, seam )
    end
    return image
end

Чтобы проверить ее в действии, воспользуемся этой функцией для сжатия нескольких изображений.

Задание 11

Функция image_carving принимает два аргумента:

сжимаемое изображение и
ширину (в пикселях), на которую мы хотим сжать изображение.

Например, чтобы сжать изображение на 200 пикселей, нужно вызвать функцию следующим образом:

new_image = image_carving(image, size(image, 2) - 200)

✏️ Задание:

Npix

200

Npix = 0 # @param {type:"slider", min:0, max:1000, step:10}

2. Затем сожмите изображение I на Npix пикселей при помощи image_carving и функции size.

3. Результат работы функции присвойте переменной Inew.

4. Отобразите I вместе с Inew.

Подсказка

Для того чтобы загрузить изображение в память, воспользуйтесь функцией load. Чтобы функция size возвращала только ширину изображения, укажите после аргумента индекс [2] или передайте число 2 вторым аргументом. Для вывода сразу двух изображений нужно передать их функции simshow аналогично следующему примеру: simshow([I1 I2]).

Решение

Inew = image_carving(I, size(I)[2] - Npix)
simshow([I Inew])

Задание 12

✏️ Задание: Повторите процедуру для изображения IMG_002.jpg. Для этого сначала выберите в выпадающем меню имя файла IMG_002.jpg

filename = "IMG_001.jpg" # @param ["IMG_001.jpg", "IMG_002.jpg", "IMG_003.jpg", "IMG_004.jpg", "IMG_005.jpg"]

Подсказка

Для того чтобы загрузить изображение в память, воспользуйтесь функцией load. Чтобы функция size возвращала только ширину изображения, укажите после аргумента индекс [2] или передайте число 2 вторым аргументом. Для вывода сразу двух изображений нужно передать их функции simshow аналогично следующему примеру: simshow([I1 I2]).

Решение

I2 = load(filename)
I2new = image_carving(I2, size(I2)[2] - Npix)
simshow([I2 I2new])

Задание 13

✏️ Задание: Напоследок, посмотрите, что случится, если сжать изображение IMG_003.jpg на 400 пикселей. Для этого сначала выберите в выпадающем меню имя файла IMG_003.jpg, а затем помощью ползунка задайте значение числа пикселей Npix, равное 400.

filename = "IMG_001.jpg" # @param ["IMG_001.jpg", "IMG_002.jpg", "IMG_003.jpg", "IMG_004.jpg", "IMG_005.jpg"]

Npix = 0 # @param {type:"slider", min:0, max:1000, step:10}

Подсказка

Для того чтобы загрузить изображение в память, воспользуйтесь функцией load. Чтобы функция size возвращала только ширину изображения, укажите после аргумента индекс [2] или передайте число 2 вторым аргументом. Для вывода сразу двух изображений нужно передать их функции simshow аналогично следующему примеру: simshow([I1 I2]).

Решение

I3 = load(filename)
I3new = image_carving(I3, size(I3)[2] - Npix)
simshow([I3 I3new])

Итог

Глядя на измененные изображения, трудно увидеть отличие от оригинальных изображений. В предыдущих заданиях мы изменяли ширину на 200 пикселей. Вы можете проверить, что будет с изображением, если сжать его и на большую величину. Алгоритм наиболее эффективен при сжатии на небольшое количество пикселей относительно всей величины изображения, иначе происходят видимые, заметные деформации изображенных объектов.

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

Данный алгоритм можно реализовать и для сжатия изображения по высоте. Один вариант – переписать код некоторых функций. Другой – просто повернуть изображение на 90 градусов перед сжатием, а потом повернуть обратно.

# Для свободной практики

Тест для получения сертификата

Пройти тест по разделу >>

Обработка изображений

Алгоритм сжатия изображений «вырезание швов»

Предобработка изображения

Определение яркости пикселей

Задание 1

Подсказка

Задание 2

Подсказка

Обнаружение границ изображенных объектов

Задание 3

Подсказка

Задание 4

Подсказка

Задание 5

Задание 6

Подсказка

Вырезание нитей

Определение положения нити

Задание 7

Задание 8

Подсказка

Задание 9

Подсказка

Задание 10

Подсказка

Алгоритм Seam Carving в действии

Проверка работы алгоритма на примерах изображений

Задание 11

Подсказка

Задание 12

Подсказка

Задание 13

Подсказка

Итог

Тест для получения сертификата

Type

Short description

Related posts

Tags

Categories

Languages

Formats

Level

Status

Published

Updated

Source