Seam Carving in Julia

4.4 μs

path_to_image

"fox.jpg"

699 ns

Functions

5.9 μs

xxxxxxxxxx
 
using Images, ImageView, ImageFiltering, Statistics, ImageMagick, PlutoUI

17.6 s

brightness (generic function with 1 method)

x
 
# Convert RGB to brigthness
function brightness(img_element::AbstractRGB)
    return mean((img_element.r + img_element.g + img_element.b))
end

22.2 μs

find_energy (generic function with 1 method)

xxxxxxxxxx
 
# Find energy, how important a pixel is to the image.
function find_energy(img)
    energy_x = imfilter(brightness.(img), Kernel.sobel()[2])
    energy_y = imfilter(brightness.(img), Kernel.sobel()[1])
    
    return sqrt.(energy_x.^2 + energy_y.^2)
end

35.2 μs

normalize_greyness (generic function with 1 method)

xxxxxxxxxx
 
# To help view energy image, normalize values to 0-1
function normalize_greyness(array)
    max, _ = findmax(array)
    array = array./max
    return array
end

26.5 μs

grey_to_rgb (generic function with 1 method)

x
 
# Convert a value to RGB to view arrays as images
function grey_to_rgb(brigthness)::RGB
    return RGB(brigthness, brigthness, brigthness)
end

30.4 μs

find_seam_at (generic function with 1 method)

xxxxxxxxxx
 
# Finds the seam of least energy starting at given position
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

28.2 μs

find_seam (generic function with 1 method)

 
# Finds the best starting point and the seam from there
function find_seam(energy)
    energy_map, next_elements = find_energy_map(energy)
    
    _, min_element = findmin(energy_map[1, :])
    
    return find_seam_at(next_elements, min_element)
end

37.4 μs

find_energy_map (generic function with 1 method)

 
# Calculate the combined energy needed for each pixel from bottom to top
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
        for 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
    end
    
    return energy_map, next_elements
end

41.8 μs

draw_seam (generic function with 1 method)

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

25.6 μs

remove_seam (generic function with 1 method)

xxxxxxxxxx
 
function remove_seam(img, seam)
    img_res = (size(img)[1], size(img)[2]-1)
    
    new_img = Array{RGB}(undef, img_res)
    
    for i = 1 :length(seam)
        if seam[i] > 1 && seam[i] < size(img)[2]
            new_img[i, :] .= vcat(img[i, 1:seam[i]-1], img[i, seam[i]+1:end])
        elseif seam[i] == 1
            new_img[i, :] .= img[i, 2:end]
        elseif seam[i] == size(img)[2]
            new_img[i, :] .= img[i, 1:end-1]
        end
    end
    return new_img
end

46.7 μs

seam_carving (generic function with 1 method)

xxxxxxxxxx
 
function seam_carving(img, res)
    if res < 0 || res > size(img)[2]
        error("resolution not acceptable")
    end
    
    for i = (1:size(img)[2] - res)
        energy = find_energy(img)
        seam = find_seam(energy)
        img = remove_seam(img, seam)
    end
    return img
end

35.1 μs

get_all_carved (generic function with 1 method)

 
# Make all carved variants of the original image
function get_all_carved(img, amount)
    
    if(amount < 0 || amount > size(img)[2])
        error("amount not acceptable")
    end
    
    all_images = []
    
    for i = (1:amount)
        energy = find_energy(img)
        seam = find_seam(energy)
        img = remove_seam(img, seam)
        push!(all_images,  img)
    end
    return all_images
end

32.2 μs

Examples

3.8 μs

The original image

8.8 μs

xxxxxxxxxx
 
begin
    test_image = imresize(load(path_to_image), ratio=1/4.5)
    test_image = RGB{Float32}.(test_image)
end

206 ms

xxxxxxxxxx
 
size(test_image)

4.8 μs

energy

459×675 Array{Float64,2}:
 0.08230626182890809   0.03924633733582069   …  0.12013708121153048
 0.08204016971261124   0.03615509192693736      0.1452321975682269
 0.06117055721409237   0.07197040239680258      0.08148767262441961
 0.1579527126513256    0.13794121945113755      0.05316306337434861
 0.14057949647072956   0.07945411130085152      0.03812833195152889
 0.21019070310238272   0.12611102359351106   …  0.16439778998489007
 0.15806071985941766   0.05101811349756884      0.09896866880767466
 ⋮                                           ⋱  
 0.030956177996254306  0.03615507091560697      0.062391724730204975
 0.06907769979945161   0.03448138488543452      0.0576724554581597
 0.023529440164585358  0.02977717948065177   …  0.04000427991459951
 0.04742507232365957   0.05030185791220897      0.057107305327577386
 0.02630661388029809   0.03553835112719368      0.027116291064753127
 0.024956750583578716  0.037203320918664774     0.04185369598012464

xxxxxxxxxx
 
energy = find_energy(test_image)

95.3 ms

This image below shows the "energy" or how important each pixel is

5.1 μs

energy_image

xxxxxxxxxx
 
energy_image = grey_to_rgb.(energy)

1.3 ms

459×675 Array{Float64,2}:
 13.4415     13.3322     13.4144     13.4028     …  5.53075     5.49632    5.52851
 13.4258     13.3592     13.293      13.3202        5.44132     5.40837    5.46554
 13.3532     13.3438     13.323      13.2763        5.42115     5.32031    5.36379
 13.3927     13.292      13.2718     13.2658        5.30259     5.32483    5.28231
 13.4433     13.2347     13.1541     13.1492        5.29658     5.22914    5.23736
 13.4577     13.3027     13.1553     13.1291     …  5.16706     5.19923    5.22769
 13.3546     13.2475     13.1766     13.0791        5.03396     5.06329    5.20093
  ⋮                                              ⋱                         
  0.14147     0.136973    0.145926    0.113835      0.13022     0.143386   0.195931
  0.15812     0.110514    0.100818    0.103997      0.0959613   0.133539   0.176819
  0.109384    0.0890423   0.0760325   0.0661278  …  0.0894212   0.119147   0.137979
  0.0961168   0.0858545   0.0592651   0.0642783     0.0850369   0.0979748  0.0989295
  0.0512634   0.0486917   0.0355526   0.0694598     0.0518985   0.0478337  0.0418222
  0.0249568   0.0372033   0.0131534   0.0587131     0.00623912  0.0147059  0.0418537

459×675 Array{Int64,2}:
 1  2  0  -1   0  -1   1   0   1   1   1  …   0  -1   0  -1   1   0  -1   1   0  -1
 1  2  1   0   1   0   1   0  -1   1   1     -1   1   1   1   0   1   0  -1   0  -1
 1  2  1   1   1   0  -1  -1  -1   1   1     -1  -1   1   1   0  -1   1   0   1   0
 1  2  1   0   1   1   0  -1  -1  -1   1     -1   1   0  -1  -1   0  -1   1   0  -1
 1  2  1   0  -1   1   1   0  -1  -1   1     -1   0  -1  -1   1   1   0  -1  -1  -1
 1  2  1   0   1   1   1   1   1   0  -1  …   1   0  -1  -1   1   1   1   0  -1  -1
 1  1  1   1   0   1   1   0  -1   1   1      0  -1  -1   0   1   1   0  -1  -1  -1
 ⋮                 ⋮                   ⋮  ⋱   ⋮                   ⋮              
 1  2  0   1   0  -1   1   0   1   1   0      0  -1  -1  -1   0  -1   0  -1  -1  -1
 1  2  1   0  -1   1   0  -1   1   0  -1     -1  -1  -1  -1  -1   0  -1   0  -1  -1
 1  2  0  -1   1   0  -1  -1   1   0  -1  …   0  -1  -1  -1  -1   0  -1   0  -1  -1
 1  2  0  -1   1   1   0  -1   1   1   0     -1  -1  -1  -1  -1   1   0   1   1   0
 0  2  0  -1  -1   1   0  -1  -1   1   0     -1   0  -1   0  -1   1   1   0  -1  -1
 0  0  0   0   0   0   0   0   0   0   0      0   0   0   0   0   0   0   0   0   0

xxxxxxxxxx
 
energy_map, next_elements = find_energy_map(energy)

29.5 ms

This image below shows the the combined energy needed for a pixel at that position.

5.9 μs

x
 
begin
    normalized = normalize_greyness(energy_map)
    energy_map_img = grey_to_rgb.(normalized)
end

2.7 ms

best_seam

Int641

450

451

452

453

454

455

456

457

458

459

xxxxxxxxxx
 
best_seam = find_seam(energy)

24.5 ms

Here the first best seam marked in red

8.2 μs

image_with_best_seam

xxxxxxxxxx
 
image_with_best_seam = draw_seam(test_image, best_seam)

788 μs

xxxxxxxxxx
 
begin
    #max_reduction = size(test_image)[2] * 0.0
    #all_carved_images = get_all_carved(test_image, max_reduction)
end

301 ns

xxxxxxxxxx
 
begin
#   width = length(all_carved_images)
#@bind new_width Slider(1:width, default=1, show_value=true)
end

300 ns

With all the carved variants we can preview each one in series.
Commented out to keep the html preview smaller. Refer to video on my website

xxxxxxxxxx
 
Text("With all the carved variants we can preview each one in series.
Commented out to keep the html preview smaller. Refer to video on my website")

5.7 μs

x
 
#all_carved_images[new_width]

300 ns

xxxxxxxxxx
 
test_image

800 ns