RensDimmendaal · September 15, 2020 01:39
diff --git a/seam-carving-object-removal.jl b/seam-carving-object-removal.jl
 ### A Pluto.jl notebook ###
 # v0.11.14

 using Markdown
 using InteractiveUtils

 # This Pluto notebook uses @bind for interactivity. When running this notebook outside of Pluto, the following 'mock version' of @bind gives bound variables a default value (instead of an error).
 macro bind(def, element)
    quote
        local el = $(esc(element))
        global $(esc(def)) = Core.applicable(Base.get, el) ? Base.get(el) : missing
        el
    end
 end

 # ╔═╡ 8adfb3dc-f64f-11ea-3ee1-15e9bf47c49b
 md"# Seam carving for object removal:
 	
 	Based on:
 	
 	* https://computationalthinking.mit.edu/Fall20/lecture3/
 	* https://github.com/fonsp/Pluto.jl/blob/master/sample/Interactivity.jl
 	"

 # ╔═╡ 877df834-f078-11ea-303b-e98273ef98a4
 begin
 	import Pkg
 	Pkg.activate(mktempdir())
 end

 # ╔═╡ 0316b94c-eef6-11ea-19bc-dbc959901bb5
 begin
 	# Poor man's Project.toml
 	Pkg.add(["Images", "ImageMagick", "PlutoUI", "ImageFiltering"])
 	
 	using Images
 	using PlutoUI
 	using ImageFiltering
 	
 	# these are "Standard Libraries" - they are included in every environment
 	using Statistics
 	using LinearAlgebra
 end

 # ╔═╡ cb335074-eef7-11ea-24e8-c39a325166a1
 md"""
 # Seam Carving

 1. We use convolution with Sobel filters for "edge detection".
 2. We use that to write an algorithm that removes "uninteresting"
   bits of an image in order to shrink it.
 """

 # ╔═╡ bf750d0e-f35c-11ea-0245-713584583fcf
 md"Select an image below!"

 # ╔═╡ 90f44be8-f35c-11ea-2fc6-c361fd4966af
 @bind image_url Select([
 "https://cdn.shortpixel.ai/spai/w_1086+q_lossy+ret_img+to_webp/https://wisetoast.com/wp-content/uploads/2015/10/The-Persistence-of-Memory-salvador-deli-painting.jpg",

 "https://upload.wikimedia.org/wikipedia/commons/thumb/1/17/Gustave_Caillebotte_-_Paris_Street%3B_Rainy_Day_-_Google_Art_Project.jpg/1014px-Gustave_Caillebotte_-_Paris_Street%3B_Rainy_Day_-_Google_Art_Project.jpg",

 "https://upload.wikimedia.org/wikipedia/commons/thumb/1/17/Gustave_Caillebotte_-_Paris_Street%3B_Rainy_Day_-_Google_Art_Project.jpg/1014px-Gustave_Caillebotte_-_Paris_Street%3B_Rainy_Day_-_Google_Art_Project.jpg",

 "https://upload.wikimedia.org/wikipedia/commons/thumb/c/cc/Grant_Wood_-_American_Gothic_-_Google_Art_Project.jpg/480px-Grant_Wood_-_American_Gothic_-_Google_Art_Project.jpg",
 		"https://cdn.shortpixel.ai/spai/w_1086+q_lossy+ret_img+to_webp/https://wisetoast.com/wp-content/uploads/2015/10/The-Persistence-of-Memory-salvador-deli-painting.jpg",

 "https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/A_Sunday_on_La_Grande_Jatte%2C_Georges_Seurat%2C_1884.jpg/640px-A_Sunday_on_La_Grande_Jatte%2C_Georges_Seurat%2C_1884.jpg",

 "https://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Van_Gogh_-_Starry_Night_-_Google_Art_Project.jpg/758px-Van_Gogh_-_Starry_Night_-_Google_Art_Project.jpg",
 		"https://web.mit.edu/facilities/photos/construction/Projects/stata/1_large.jpg",
 	])

 # ╔═╡ d2ae6dd2-eef9-11ea-02df-255ec3b46a36
 img = load(download(image_url))

 # ╔═╡ 8ded023c-f35c-11ea-317c-11f5d1b67998


 # ╔═╡ 0b6010a8-eef6-11ea-3ad6-c1f10e30a413
 # arbitrarily choose the brightness of a pixel as mean of rgb
 # brightness(c::AbstractRGB) = mean((c.r, c.g, c.b))

 # Use a weighted sum of rgb giving more weight to colors we perceive as 'brighter'
 # Based on https://www.tutorialspoint.com/dip/grayscale_to_rgb_conversion.htm
 brightness(c::AbstractRGB) = 0.3 * c.r + 0.59 * c.g + 0.11 * c.b

 # ╔═╡ fc1c43cc-eef6-11ea-0fc4-a90ac4336964
 Gray.(brightness.(img))

 # ╔═╡ 82c0d0c8-efec-11ea-1bb9-83134ecb877e
 md"""
 # Edge detection filter

 (Spoiler alert!) Here, we use the Sobel edge detection filter we created in Homework 1.

 ```math
 \begin{align}

 G_x &= \begin{bmatrix}
 1 & 0 & -1 \\
 2 & 0 & -2 \\
 1 & 0 & -1 \\
 \end{bmatrix}*A\\
 G_y &= \begin{bmatrix}
 1 & 2 & 1 \\
 0 & 0 & 0 \\
 -1 & -2 & -1 \\
 \end{bmatrix}*A
 \end{align}
 ```
 Here $A$ is the array corresponding to your image.
 We can think of these as derivatives in the $x$ and $y$ directions.

 Then we combine them by finding the magnitude of the **gradient** (in the sense of multivariate calculus) by defining

 $$G_\text{total} = \sqrt{G_x^2 + G_y^2}.$$
 """

 # ╔═╡ da726954-eff0-11ea-21d4-a7f4ae4a6b09
 Sy, Sx = Kernel.sobel()

 # ╔═╡ abf6944e-f066-11ea-18e2-0b92606dab85
 (collect(Int.(8 .* Sy)), collect(Int.(8 .* Sx)))

 # ╔═╡ ac8d6902-f069-11ea-0f1d-9b0fa706d769
 md"""
 - blue shows positive values
 - red shows negative values
 $G_x \hspace{180pt} G_y$
 """

 # ╔═╡ 172c7612-efee-11ea-077a-5d5c6e2505a4
 function shrink_image(image, ratio=5)
 	(height, width) = size(image)
 	new_height = height ÷ ratio - 1
 	new_width = width ÷ ratio - 1
 	list = [
 		mean(image[
 			ratio * i:ratio * (i + 1),
 			ratio * j:ratio * (j + 1),
 		])
 		for j in 1:new_width
 		for i in 1:new_height
 	]
 	reshape(list, new_height, new_width)
 end

 # ╔═╡ fcf46120-efec-11ea-06b9-45f470899cb2
 function convolve(M, kernel)
    height, width = size(kernel)
    
    half_height = height ÷ 2
    half_width = width ÷ 2
    
    new_image = similar(M)
 	
    # (i, j) loop over the original image
 	m, n = size(M)
    @inbounds for i in 1:m
        for j in 1:n
            # (k, l) loop over the neighbouring pixels
 			accumulator = 0 * M[1, 1]
 			for k in -half_height:-half_height + height - 1
 				for l in -half_width:-half_width + width - 1
 					Mi = i - k
 					Mj = j - l
 					# First index into M
 					if Mi < 1
 						Mi = 1
 					elseif Mi > m
 						Mi = m
 					end
 					# Second index into M
 					if Mj < 1
 						Mj = 1
 					elseif Mj > n
 						Mj = n
 					end
 					
 					accumulator += kernel[k, l] * M[Mi, Mj]
 				end
 			end
 			new_image[i, j] = accumulator
        end
    end
    
    return new_image
 end

 # ╔═╡ 6f7bd064-eff4-11ea-0260-f71aa7f4f0e5
 function edgeness(img)
 	Sy, Sx = Kernel.sobel()
 	b = brightness.(img)

 	∇y = convolve(b, Sy)
 	∇x = convolve(b, Sx)

 	sqrt.(∇x.^2 + ∇y.^2)
 end

 # ╔═╡ dec62538-efee-11ea-1e03-0b801e61e91c
 	function show_colored_array(array)
 		pos_color = RGB(0.36, 0.82, 0.8)
 		neg_color = RGB(0.99, 0.18, 0.13)
 		to_rgb(x) = max(x, 0) * pos_color + max(-x, 0) * neg_color
 		to_rgb.(array) / maximum(abs.(array))
 	end

 # ╔═╡ da39c824-eff0-11ea-375b-1b6c6e186182
 # Sx
 # collect(Int.(8 .* Sx))
 show_colored_array(Sx)

 # ╔═╡ 074a58be-f146-11ea-382c-b7ae6c44bf75
 # Sy
 # collect(Int.(8 .* Sy))
 show_colored_array(Sy)

 # ╔═╡ f8283a0e-eff4-11ea-23d3-9f1ced1bafb4
 md"""

 ## Seam carving idea

 The idea of seam carving is to find a path from the top of the image to the bottom of the image where the path minimizes the edgness.

 In other words, this path **minimizes the number of edges it crosses**
 """

 # ╔═╡ 025e2c94-eefb-11ea-12cb-f56f34886334
 md"""

 At every step in going down, the path is allowed to go south west, south or south east. We want to find a seam with the minimum possible sum of energies.

 We start by writing a `least_edgy` function which given a matrix of energies, returns
 a matrix of minimum possible energy starting from that pixel going up to a pixel in the bottom most row.
 """

 # ╔═╡ acc1ee8c-eef9-11ea-01ac-9b9e9c4167b3
 #            e[x,y] 
 #          ↙   ↓   ↘       <--pick the next path which gives the least overall energy
 #  e[x-1,y+1] e[x,y+1]  e[x+1,y+1]     
 #
 # Basic Comp:   e[x,y] += min( e[x-1,y+1],e[x,y],e[x+1,y])
 #               dirs records which one from (-1==SW,0==S,1==SE)

 function least_edgy(E)
 	least_E = zeros(size(E))
 	dirs = zeros(Int, size(E))
 	least_E[end, :] .= E[end, :] # the minimum energy on the last row is the energy
 	                             # itself

 	m, n = size(E)
 	# Go from the last row up, finding the minimum energy
 	for i in m-1:-1:1
 		for j in 1:n
 			j1, j2 = max(1, j-1), min(j+1, n)
 			e, dir = findmin(least_E[i+1, j1:j2])
 			least_E[i,j] += e
 			least_E[i,j] += E[i,j]
 			dirs[i, j] = (-1,0,1)[dir + (j==1)]
 		end
 	end
 	least_E, dirs
 end

 # ╔═╡ 8b204a2a-eff6-11ea-25b0-13f230037ee1
 # The bright areas are screaming "AVOID ME!!!"
 least_e, dirs = least_edgy(edgeness(img))

 # ╔═╡ 84d3afe4-eefe-11ea-1e31-bf3b2af4aecd
 show_colored_array(least_e)

 # ╔═╡ b507480a-ef01-11ea-21c4-63d19fac19ab
 # direction the path should take at every pixel.
 reduce((x,y)->x*y*"\n",
 	reduce(*, getindex.(([" ", "↙", "↓", "↘"],), dirs[1:25, 1:60].+3), dims=2, init=""), init="") |> Text

 # ╔═╡ 7d8b20a2-ef03-11ea-1c9e-fdf49a397619
 md"## Remove seams"

 # ╔═╡ f690b06a-ef31-11ea-003b-4f2b2f82a9c3
 md"""
 Compressing an image horizontally involves a number of seams of lowest energy successively.
 """

 # ╔═╡ 977b6b98-ef03-11ea-0176-551fc29729ab
 function get_seam_at(dirs, j)
 	m = size(dirs, 1)
 	js = fill(0, m)
 	js[1] = j
 	for i=2:m
 		js[i] = js[i-1] + dirs[i-1, js[i-1]]
 	end
 	tuple.(1:m, js)
 end

 # ╔═╡ 9abbb158-ef03-11ea-39df-a3e8aa792c50
 get_seam_at(dirs, 2)

 # ╔═╡ 14f72976-ef05-11ea-2ad5-9f0914f9cf58
 function mark_path(img, path)
 	img′ = copy(img)
 	m = size(img, 2)
 	for (i, j) in path
 		# To make it easier to see, we'll color not just
 		# the pixels of the seam, but also those adjacent to it
 		for j′ in j-1:j+1
 			img′[i, clamp(j′, 1, m)] = RGB(1,0,1)
 		end
 	end
 	img′
 end

 # ╔═╡ cf9a9124-ef04-11ea-14a4-abf930edc7cc
 @bind start_column Slider(1:size(img, 2))

 # ╔═╡ 772a4d68-ef04-11ea-366a-f7ae9e1634f6
 path = get_seam_at(dirs, start_column)

 # ╔═╡ 081a98cc-f06e-11ea-3664-7ba51d4fd153
 function pencil(X)
 	f(x) = RGB(1-x,1-x,1-x)
 	map(f, X ./ maximum(X))
 end

 # ╔═╡ 237647e8-f06d-11ea-3c7e-2da57e08bebc
 e = edgeness(img);

 # ╔═╡ 4f23bc54-ef0f-11ea-06a9-35ca3ece421e
 function rm_path(img, path)
 	img′ = img[:, 1:end-1] # one less column
 	for (i, j) in path
 		img′[i, 1:j-1] .= img[i, 1:j-1]
 		img′[i, j:end] .= img[i, j+1:end]
 	end
 	img′
 end

 # ╔═╡ b1b6b7fc-f153-11ea-224a-2578e8298775
 n_examples = min(300, size(img, 2))

 # ╔═╡ e2cba094-f5fd-11ea-096d-37fe5fec7e8f
 md"# Mark what you want to remove"

 # ╔═╡ dc1bfcf8-f5fd-11ea-098d-b12fd21bb9df
 @bind canvas html"""
 <canvas width="200" height="200" style="position: relative"></canvas>

 <script>
 // 🐸 `this` is the cell output wrapper - we use it to select elements 🐸 //

 const canvas = this.querySelector("canvas")
 const ctx = canvas.getContext("2d")

 var startX = 80
 var startY = 40
 var foo = 999

 canvas.width = 788;
 canvas.height = 599;

 var background = new Image();
 background.src = "https://cdn.shortpixel.ai/spai/w_1086+q_lossy+ret_img+to_webp/https://wisetoast.com/wp-content/uploads/2015/10/The-Persistence-of-Memory-salvador-deli-painting.jpg";

 // Make sure the image is loaded first otherwise nothing will draw.
 background.onload = function(){
    ctx.drawImage(background,0,0);   
 }
 // Draw whatever else over top of it on the canvas

 function onmove(e){
 	// 🐸 We send the value back to Julia 🐸 //
 	canvas.value = [startX, startY, e.layerX - startX, e.layerY - startY]
 	canvas.dispatchEvent(new CustomEvent("input"))

 	ctx.clearRect(0, 0, canvas.width, canvas.height);
 	ctx.drawImage(background,0,0);
 	ctx.fillStyle = '#3f3d6d'
 	ctx.fillRect(...canvas.value)
 }

 canvas.onmousedown = e => {
 	startX = e.layerX
 	startY = e.layerY
 	canvas.onmousemove = onmove
 }

 canvas.onmouseup = e => {
 	canvas.onmousemove = null
 }

 // Fire a fake mousemoveevent to show something
 onmove({layerX: 130, layerY: 160})

 </script>
 """

 # ╔═╡ b401f398-ef0f-11ea-38fe-012b7bc8a4fa
 function shrink_n(img, n)
 	imgs = []
 	marked_imgs = []

 	e = edgeness(img)
 	
 	# start -- hardcoded removal of the top clock!
 	e[canvas[2]:(canvas[2]+canvas[4]),canvas[1]:(canvas[1]+canvas[3])] .= 0
 	# end
 	
 	for i=1:n
 		least_E, dirs = least_edgy(e)
 		_, min_j = findmin(@view least_E[1, :])
 		seam = get_seam_at(dirs, min_j)
 		img = rm_path(img, seam)
 		# Recompute the energy for the new image
 		# Note, this currently involves rerunning the convolution
 		# on the whole image, but in principle the only values that
 		# need recomputation are those adjacent to the seam, so there
 		# is room for a meanintful speedup here.
 #		e = edgeness(img)
 		e = rm_path(e, seam)

 		push!(imgs, img)
 		push!(marked_imgs, mark_path(img, seam))
 	end
 	imgs, marked_imgs
 end

 # ╔═╡ 2eb459d4-ef36-11ea-1f74-b53ffec7a1ed
 # returns two vectors of n successively smaller images
 # The second images have markings where the seam is cut out
 carved, marked_carved = shrink_n(img, n_examples);

 # ╔═╡ 7038abe4-ef36-11ea-11a5-75e57ab51032
 @bind n Slider(1:length(carved))

 # ╔═╡ 2d6c6820-ef2d-11ea-1704-49bb5188cfcc
 md"shrunk by $n:"

 # ╔═╡ 1fd26a60-f089-11ea-1f56-bb6eba7d9651
 function hbox(x, y, gap=16; sy=size(y), sx=size(x))
 	w,h = (max(sx[1], sy[1]),
 		   gap + sx[2] + sy[2])
 	
 	slate = fill(RGB(1,1,1), w,h)
 	slate[1:size(x,1), 1:size(x,2)] .= RGB.(x)
 	slate[1:size(y,1), size(x,2) + gap .+ (1:size(y,2))] .= RGB.(y)
 	slate
 end

 # ╔═╡ 44192a40-eff2-11ea-0ec7-05cdadb0c29a
 begin
 	img_brightness = brightness.(img)
 	∇x = convolve(img_brightness, Sx)
 	∇y = convolve(img_brightness, Sy)
 	hbox(show_colored_array(∇x), show_colored_array(∇y))
 end

 # ╔═╡ d6a268c0-eff4-11ea-2c9e-bfef19c7f540
 begin
 	edged = edgeness(img)
 	# hbox(img, pencil(edged))
 	hbox(img, Gray.(edgeness(img)) / maximum(abs.(edged)))
 end

 # ╔═╡ 552fb92e-ef05-11ea-0a79-dd7a6760089a
 hbox(mark_path(img, path), mark_path(show_colored_array(least_e), path))

 # ╔═╡ dfd03c4e-f06c-11ea-1e2a-89233a675138
 let
 	hbox(mark_path(img, path), mark_path(pencil(e), path));
 end

 # ╔═╡ ca4a87e8-eff8-11ea-3d57-01dfa34ff723
 let
 	# least energy path of them all:
 	_, k = findmin(least_e[1, :])
 	path = get_seam_at(dirs, k)
 	hbox(
 		mark_path(img, path),
 		mark_path(show_colored_array(least_e), path)
 	)
 end

 # ╔═╡ fa6a2152-ef0f-11ea-0e67-0d1a6599e779
 hbox(img, marked_carved[n], sy=size(img))

 # ╔═╡ 71b16dbe-f08b-11ea-2343-5f1583074029
 vbox(x,y, gap=16) = hbox(x', y')'

 # ╔═╡ ddac52ea-f148-11ea-2860-21cff4c867e6
 let
 	∇y = convolve(brightness.(img), Sy)
 	∇x = convolve(brightness.(img), Sx)
 	# zoom in on the clock
 	vbox(
 		hbox(img[300:end, 1:300], img[300:end, 1:300]), 
 	 	hbox(show_colored_array.((∇x[300:end,  1:300], ∇y[300:end, 1:300]))...)
 	)
 end

 # ╔═╡ 15d1e5dc-ef2f-11ea-093a-417108bcd495
 [size(img) size(carved[n])]

 # ╔═╡ 7e8084f4-f64f-11ea-322a-95f73f207421
 canvas

 # ╔═╡ 01d98866-f5cc-11ea-1010-57120dca4270
 begin
 	mask = copy(img)
 	mask[canvas[2]:(canvas[2]+canvas[4]),canvas[1]:(canvas[1]+canvas[3])] .= 0
 	mask
 end

 # ╔═╡ Cell order:
 # ╟─8adfb3dc-f64f-11ea-3ee1-15e9bf47c49b
 # ╟─877df834-f078-11ea-303b-e98273ef98a4
 # ╟─0316b94c-eef6-11ea-19bc-dbc959901bb5
 # ╟─cb335074-eef7-11ea-24e8-c39a325166a1
 # ╟─bf750d0e-f35c-11ea-0245-713584583fcf
 # ╠═90f44be8-f35c-11ea-2fc6-c361fd4966af
 # ╟─d2ae6dd2-eef9-11ea-02df-255ec3b46a36
 # ╠═8ded023c-f35c-11ea-317c-11f5d1b67998
 # ╟─0b6010a8-eef6-11ea-3ad6-c1f10e30a413
 # ╠═fc1c43cc-eef6-11ea-0fc4-a90ac4336964
 # ╟─82c0d0c8-efec-11ea-1bb9-83134ecb877e
 # ╠═da726954-eff0-11ea-21d4-a7f4ae4a6b09
 # ╠═da39c824-eff0-11ea-375b-1b6c6e186182
 # ╠═074a58be-f146-11ea-382c-b7ae6c44bf75
 # ╠═abf6944e-f066-11ea-18e2-0b92606dab85
 # ╠═44192a40-eff2-11ea-0ec7-05cdadb0c29a
 # ╟─ac8d6902-f069-11ea-0f1d-9b0fa706d769
 # ╠═ddac52ea-f148-11ea-2860-21cff4c867e6
 # ╠═6f7bd064-eff4-11ea-0260-f71aa7f4f0e5
 # ╟─d6a268c0-eff4-11ea-2c9e-bfef19c7f540
 # ╟─172c7612-efee-11ea-077a-5d5c6e2505a4
 # ╟─fcf46120-efec-11ea-06b9-45f470899cb2
 # ╟─dec62538-efee-11ea-1e03-0b801e61e91c
 # ╟─f8283a0e-eff4-11ea-23d3-9f1ced1bafb4
 # ╟─025e2c94-eefb-11ea-12cb-f56f34886334
 # ╠═acc1ee8c-eef9-11ea-01ac-9b9e9c4167b3
 # ╠═8b204a2a-eff6-11ea-25b0-13f230037ee1
 # ╠═84d3afe4-eefe-11ea-1e31-bf3b2af4aecd
 # ╠═b507480a-ef01-11ea-21c4-63d19fac19ab
 # ╟─7d8b20a2-ef03-11ea-1c9e-fdf49a397619
 # ╠═f690b06a-ef31-11ea-003b-4f2b2f82a9c3
 # ╠═977b6b98-ef03-11ea-0176-551fc29729ab
 # ╠═9abbb158-ef03-11ea-39df-a3e8aa792c50
 # ╠═772a4d68-ef04-11ea-366a-f7ae9e1634f6
 # ╠═14f72976-ef05-11ea-2ad5-9f0914f9cf58
 # ╠═cf9a9124-ef04-11ea-14a4-abf930edc7cc
 # ╠═552fb92e-ef05-11ea-0a79-dd7a6760089a
 # ╠═081a98cc-f06e-11ea-3664-7ba51d4fd153
 # ╠═237647e8-f06d-11ea-3c7e-2da57e08bebc
 # ╠═dfd03c4e-f06c-11ea-1e2a-89233a675138
 # ╠═ca4a87e8-eff8-11ea-3d57-01dfa34ff723
 # ╠═4f23bc54-ef0f-11ea-06a9-35ca3ece421e
 # ╠═b401f398-ef0f-11ea-38fe-012b7bc8a4fa
 # ╠═b1b6b7fc-f153-11ea-224a-2578e8298775
 # ╠═2eb459d4-ef36-11ea-1f74-b53ffec7a1ed
 # ╟─e2cba094-f5fd-11ea-096d-37fe5fec7e8f
 # ╟─dc1bfcf8-f5fd-11ea-098d-b12fd21bb9df
 # ╠═7038abe4-ef36-11ea-11a5-75e57ab51032
 # ╟─2d6c6820-ef2d-11ea-1704-49bb5188cfcc
 # ╠═fa6a2152-ef0f-11ea-0e67-0d1a6599e779
 # ╟─71b16dbe-f08b-11ea-2343-5f1583074029
 # ╟─1fd26a60-f089-11ea-1f56-bb6eba7d9651
 # ╠═15d1e5dc-ef2f-11ea-093a-417108bcd495
 # ╠═7e8084f4-f64f-11ea-322a-95f73f207421
 # ╠═01d98866-f5cc-11ea-1010-57120dca4270
	### A Pluto.jl notebook ###
	# v0.11.14

	using Markdown
	using InteractiveUtils

	# This Pluto notebook uses @bind for interactivity. When running this notebook outside of Pluto, the following 'mock version' of @bind gives bound variables a default value (instead of an error).
	macro bind(def, element)
	quote
	local el = $(esc(element))
	global $(esc(def)) = Core.applicable(Base.get, el) ? Base.get(el) : missing
	el
	end
	end

	# ╔═╡ 8adfb3dc-f64f-11ea-3ee1-15e9bf47c49b
	md"# Seam carving for object removal:

	Based on:

	* https://computationalthinking.mit.edu/Fall20/lecture3/
	* https://github.com/fonsp/Pluto.jl/blob/master/sample/Interactivity.jl
	"

	# ╔═╡ 877df834-f078-11ea-303b-e98273ef98a4
	begin
	import Pkg
	Pkg.activate(mktempdir())
	end

	# ╔═╡ 0316b94c-eef6-11ea-19bc-dbc959901bb5
	begin
	# Poor man's Project.toml
	Pkg.add(["Images", "ImageMagick", "PlutoUI", "ImageFiltering"])

	using Images
	using PlutoUI
	using ImageFiltering

	# these are "Standard Libraries" - they are included in every environment
	using Statistics
	using LinearAlgebra
	end

	# ╔═╡ cb335074-eef7-11ea-24e8-c39a325166a1
	md"""
	# Seam Carving

	1. We use convolution with Sobel filters for "edge detection".
	2. We use that to write an algorithm that removes "uninteresting"
	bits of an image in order to shrink it.
	"""

	# ╔═╡ bf750d0e-f35c-11ea-0245-713584583fcf
	md"Select an image below!"

	# ╔═╡ 90f44be8-f35c-11ea-2fc6-c361fd4966af
	@bind image_url Select([
	"https://cdn.shortpixel.ai/spai/w_1086+q_lossy+ret_img+to_webp/https://wisetoast.com/wp-content/uploads/2015/10/The-Persistence-of-Memory-salvador-deli-painting.jpg",

	"https://upload.wikimedia.org/wikipedia/commons/thumb/1/17/Gustave_Caillebotte_-_Paris_Street%3B_Rainy_Day_-_Google_Art_Project.jpg/1014px-Gustave_Caillebotte_-_Paris_Street%3B_Rainy_Day_-_Google_Art_Project.jpg",

	"https://upload.wikimedia.org/wikipedia/commons/thumb/1/17/Gustave_Caillebotte_-_Paris_Street%3B_Rainy_Day_-_Google_Art_Project.jpg/1014px-Gustave_Caillebotte_-_Paris_Street%3B_Rainy_Day_-_Google_Art_Project.jpg",

	"https://upload.wikimedia.org/wikipedia/commons/thumb/c/cc/Grant_Wood_-_American_Gothic_-_Google_Art_Project.jpg/480px-Grant_Wood_-_American_Gothic_-_Google_Art_Project.jpg",
	"https://cdn.shortpixel.ai/spai/w_1086+q_lossy+ret_img+to_webp/https://wisetoast.com/wp-content/uploads/2015/10/The-Persistence-of-Memory-salvador-deli-painting.jpg",

	"https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/A_Sunday_on_La_Grande_Jatte%2C_Georges_Seurat%2C_1884.jpg/640px-A_Sunday_on_La_Grande_Jatte%2C_Georges_Seurat%2C_1884.jpg",

	"https://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Van_Gogh_-_Starry_Night_-_Google_Art_Project.jpg/758px-Van_Gogh_-_Starry_Night_-_Google_Art_Project.jpg",
	"https://web.mit.edu/facilities/photos/construction/Projects/stata/1_large.jpg",
	])

	# ╔═╡ d2ae6dd2-eef9-11ea-02df-255ec3b46a36
	img = load(download(image_url))

	# ╔═╡ 8ded023c-f35c-11ea-317c-11f5d1b67998


	# ╔═╡ 0b6010a8-eef6-11ea-3ad6-c1f10e30a413
	# arbitrarily choose the brightness of a pixel as mean of rgb
	# brightness(c::AbstractRGB) = mean((c.r, c.g, c.b))

	# Use a weighted sum of rgb giving more weight to colors we perceive as 'brighter'
	# Based on https://www.tutorialspoint.com/dip/grayscale_to_rgb_conversion.htm
	brightness(c::AbstractRGB) = 0.3 * c.r + 0.59 * c.g + 0.11 * c.b

	# ╔═╡ fc1c43cc-eef6-11ea-0fc4-a90ac4336964
	Gray.(brightness.(img))

	# ╔═╡ 82c0d0c8-efec-11ea-1bb9-83134ecb877e
	md"""
	# Edge detection filter

	(Spoiler alert!) Here, we use the Sobel edge detection filter we created in Homework 1.

	```math
	\begin{align}

	G_x &= \begin{bmatrix}
	1 & 0 & -1 \\
	2 & 0 & -2 \\
	1 & 0 & -1 \\
	\end{bmatrix}*A\\
	G_y &= \begin{bmatrix}
	1 & 2 & 1 \\
	0 & 0 & 0 \\
	-1 & -2 & -1 \\
	\end{bmatrix}*A
	\end{align}
	```
	Here $A$ is the array corresponding to your image.
	We can think of these as derivatives in the $x$ and $y$ directions.

	Then we combine them by finding the magnitude of the gradient (in the sense of multivariate calculus) by defining

	$$G_\text{total} = \sqrt{G_x^2 + G_y^2}.$$
	"""

	# ╔═╡ da726954-eff0-11ea-21d4-a7f4ae4a6b09
	Sy, Sx = Kernel.sobel()

	# ╔═╡ abf6944e-f066-11ea-18e2-0b92606dab85
	(collect(Int.(8 .* Sy)), collect(Int.(8 .* Sx)))

	# ╔═╡ ac8d6902-f069-11ea-0f1d-9b0fa706d769
	md"""
	- blue shows positive values
	- red shows negative values
	$G_x \hspace{180pt} G_y$
	"""

	# ╔═╡ 172c7612-efee-11ea-077a-5d5c6e2505a4
	function shrink_image(image, ratio=5)
	(height, width) = size(image)
	new_height = height ÷ ratio - 1
	new_width = width ÷ ratio - 1
	list = [
	mean(image[
	ratio * i:ratio * (i + 1),
	ratio * j:ratio * (j + 1),
	])
	for j in 1:new_width
	for i in 1:new_height
	]
	reshape(list, new_height, new_width)
	end

	# ╔═╡ fcf46120-efec-11ea-06b9-45f470899cb2
	function convolve(M, kernel)
	height, width = size(kernel)

	half_height = height ÷ 2
	half_width = width ÷ 2

	new_image = similar(M)

	# (i, j) loop over the original image
	m, n = size(M)
	@inbounds for i in 1:m
	for j in 1:n
	# (k, l) loop over the neighbouring pixels
	accumulator = 0 * M[1, 1]
	for k in -half_height:-half_height + height - 1
	for l in -half_width:-half_width + width - 1
	Mi = i - k
	Mj = j - l
	# First index into M
	if Mi < 1
	Mi = 1
	elseif Mi > m
	Mi = m
	end
	# Second index into M
	if Mj < 1
	Mj = 1
	elseif Mj > n
	Mj = n
	end

	accumulator += kernel[k, l] * M[Mi, Mj]
	end
	end
	new_image[i, j] = accumulator
	end
	end

	return new_image
	end

	# ╔═╡ 6f7bd064-eff4-11ea-0260-f71aa7f4f0e5
	function edgeness(img)
	Sy, Sx = Kernel.sobel()
	b = brightness.(img)

	∇y = convolve(b, Sy)
	∇x = convolve(b, Sx)

	sqrt.(∇x.^2 + ∇y.^2)
	end

	# ╔═╡ dec62538-efee-11ea-1e03-0b801e61e91c
	function show_colored_array(array)
	pos_color = RGB(0.36, 0.82, 0.8)
	neg_color = RGB(0.99, 0.18, 0.13)
	to_rgb(x) = max(x, 0) * pos_color + max(-x, 0) * neg_color
	to_rgb.(array) / maximum(abs.(array))
	end

	# ╔═╡ da39c824-eff0-11ea-375b-1b6c6e186182
	# Sx
	# collect(Int.(8 .* Sx))
	show_colored_array(Sx)

	# ╔═╡ 074a58be-f146-11ea-382c-b7ae6c44bf75
	# Sy
	# collect(Int.(8 .* Sy))
	show_colored_array(Sy)

	# ╔═╡ f8283a0e-eff4-11ea-23d3-9f1ced1bafb4
	md"""

	## Seam carving idea

	The idea of seam carving is to find a path from the top of the image to the bottom of the image where the path minimizes the edgness.

	In other words, this path minimizes the number of edges it crosses
	"""

	# ╔═╡ 025e2c94-eefb-11ea-12cb-f56f34886334
	md"""

	At every step in going down, the path is allowed to go south west, south or south east. We want to find a seam with the minimum possible sum of energies.

	We start by writing a `least_edgy` function which given a matrix of energies, returns
	a matrix of minimum possible energy starting from that pixel going up to a pixel in the bottom most row.
	"""

	# ╔═╡ acc1ee8c-eef9-11ea-01ac-9b9e9c4167b3
	# e[x,y]
	# ↙ ↓ ↘ <--pick the next path which gives the least overall energy
	# e[x-1,y+1] e[x,y+1] e[x+1,y+1]
	#
	# Basic Comp: e[x,y] += min( e[x-1,y+1],e[x,y],e[x+1,y])
	# dirs records which one from (-1==SW,0==S,1==SE)

	function least_edgy(E)
	least_E = zeros(size(E))
	dirs = zeros(Int, size(E))
	least_E[end, :] .= E[end, :] # the minimum energy on the last row is the energy
	# itself

	m, n = size(E)
	# Go from the last row up, finding the minimum energy
	for i in m-1:-1:1
	for j in 1:n
	j1, j2 = max(1, j-1), min(j+1, n)
	e, dir = findmin(least_E[i+1, j1:j2])
	least_E[i,j] += e
	least_E[i,j] += E[i,j]
	dirs[i, j] = (-1,0,1)[dir + (j==1)]
	end
	end
	least_E, dirs
	end

	# ╔═╡ 8b204a2a-eff6-11ea-25b0-13f230037ee1
	# The bright areas are screaming "AVOID ME!!!"
	least_e, dirs = least_edgy(edgeness(img))

	# ╔═╡ 84d3afe4-eefe-11ea-1e31-bf3b2af4aecd
	show_colored_array(least_e)

	# ╔═╡ b507480a-ef01-11ea-21c4-63d19fac19ab
	# direction the path should take at every pixel.
	reduce((x,y)->xy"\n",
	reduce(*, getindex.(([" ", "↙", "↓", "↘"],), dirs[1:25, 1:60].+3), dims=2, init=""), init="") \|> Text

	# ╔═╡ 7d8b20a2-ef03-11ea-1c9e-fdf49a397619
	md"## Remove seams"

	# ╔═╡ f690b06a-ef31-11ea-003b-4f2b2f82a9c3
	md"""
	Compressing an image horizontally involves a number of seams of lowest energy successively.
	"""

	# ╔═╡ 977b6b98-ef03-11ea-0176-551fc29729ab
	function get_seam_at(dirs, j)
	m = size(dirs, 1)
	js = fill(0, m)
	js[1] = j
	for i=2:m
	js[i] = js[i-1] + dirs[i-1, js[i-1]]
	end
	tuple.(1:m, js)
	end

	# ╔═╡ 9abbb158-ef03-11ea-39df-a3e8aa792c50
	get_seam_at(dirs, 2)

	# ╔═╡ 14f72976-ef05-11ea-2ad5-9f0914f9cf58
	function mark_path(img, path)
	img′ = copy(img)
	m = size(img, 2)
	for (i, j) in path
	# To make it easier to see, we'll color not just
	# the pixels of the seam, but also those adjacent to it
	for j′ in j-1:j+1
	img′[i, clamp(j′, 1, m)] = RGB(1,0,1)
	end
	end
	img′
	end

	# ╔═╡ cf9a9124-ef04-11ea-14a4-abf930edc7cc
	@bind start_column Slider(1:size(img, 2))

	# ╔═╡ 772a4d68-ef04-11ea-366a-f7ae9e1634f6
	path = get_seam_at(dirs, start_column)

	# ╔═╡ 081a98cc-f06e-11ea-3664-7ba51d4fd153
	function pencil(X)
	f(x) = RGB(1-x,1-x,1-x)
	map(f, X ./ maximum(X))
	end

	# ╔═╡ 237647e8-f06d-11ea-3c7e-2da57e08bebc
	e = edgeness(img);

	# ╔═╡ 4f23bc54-ef0f-11ea-06a9-35ca3ece421e
	function rm_path(img, path)
	img′ = img[:, 1:end-1] # one less column
	for (i, j) in path
	img′[i, 1:j-1] .= img[i, 1:j-1]
	img′[i, j:end] .= img[i, j+1:end]
	end
	img′
	end

	# ╔═╡ b1b6b7fc-f153-11ea-224a-2578e8298775
	n_examples = min(300, size(img, 2))

	# ╔═╡ e2cba094-f5fd-11ea-096d-37fe5fec7e8f
	md"# Mark what you want to remove"

	# ╔═╡ dc1bfcf8-f5fd-11ea-098d-b12fd21bb9df
	@bind canvas html"""
	<canvas width="200" height="200" style="position: relative"></canvas>

	<script>
	// 🐸 `this` is the cell output wrapper - we use it to select elements 🐸 //

	const canvas = this.querySelector("canvas")
	const ctx = canvas.getContext("2d")

	var startX = 80
	var startY = 40
	var foo = 999

	canvas.width = 788;
	canvas.height = 599;

	var background = new Image();
	background.src = "https://cdn.shortpixel.ai/spai/w_1086+q_lossy+ret_img+to_webp/https://wisetoast.com/wp-content/uploads/2015/10/The-Persistence-of-Memory-salvador-deli-painting.jpg";

	// Make sure the image is loaded first otherwise nothing will draw.
	background.onload = function(){
	ctx.drawImage(background,0,0);
	}
	// Draw whatever else over top of it on the canvas

	function onmove(e){
	// 🐸 We send the value back to Julia 🐸 //
	canvas.value = [startX, startY, e.layerX - startX, e.layerY - startY]
	canvas.dispatchEvent(new CustomEvent("input"))

	ctx.clearRect(0, 0, canvas.width, canvas.height);
	ctx.drawImage(background,0,0);
	ctx.fillStyle = '#3f3d6d'
	ctx.fillRect(...canvas.value)
	}

	canvas.onmousedown = e => {
	startX = e.layerX
	startY = e.layerY
	canvas.onmousemove = onmove
	}

	canvas.onmouseup = e => {
	canvas.onmousemove = null
	}

	// Fire a fake mousemoveevent to show something
	onmove({layerX: 130, layerY: 160})

	</script>
	"""

	# ╔═╡ b401f398-ef0f-11ea-38fe-012b7bc8a4fa
	function shrink_n(img, n)
	imgs = []
	marked_imgs = []

	e = edgeness(img)

	# start -- hardcoded removal of the top clock!
	e[canvas[2]:(canvas[2]+canvas[4]),canvas[1]:(canvas[1]+canvas[3])] .= 0
	# end

	for i=1:n
	least_E, dirs = least_edgy(e)
	_, min_j = findmin(@view least_E[1, :])
	seam = get_seam_at(dirs, min_j)
	img = rm_path(img, seam)
	# Recompute the energy for the new image
	# Note, this currently involves rerunning the convolution
	# on the whole image, but in principle the only values that
	# need recomputation are those adjacent to the seam, so there
	# is room for a meanintful speedup here.
	# e = edgeness(img)
	e = rm_path(e, seam)

	push!(imgs, img)
	push!(marked_imgs, mark_path(img, seam))
	end
	imgs, marked_imgs
	end

	# ╔═╡ 2eb459d4-ef36-11ea-1f74-b53ffec7a1ed
	# returns two vectors of n successively smaller images
	# The second images have markings where the seam is cut out
	carved, marked_carved = shrink_n(img, n_examples);

	# ╔═╡ 7038abe4-ef36-11ea-11a5-75e57ab51032
	@bind n Slider(1:length(carved))

	# ╔═╡ 2d6c6820-ef2d-11ea-1704-49bb5188cfcc
	md"shrunk by $n:"

	# ╔═╡ 1fd26a60-f089-11ea-1f56-bb6eba7d9651
	function hbox(x, y, gap=16; sy=size(y), sx=size(x))
	w,h = (max(sx[1], sy[1]),
	gap + sx[2] + sy[2])

	slate = fill(RGB(1,1,1), w,h)
	slate[1:size(x,1), 1:size(x,2)] .= RGB.(x)
	slate[1:size(y,1), size(x,2) + gap .+ (1:size(y,2))] .= RGB.(y)
	slate
	end

	# ╔═╡ 44192a40-eff2-11ea-0ec7-05cdadb0c29a
	begin
	img_brightness = brightness.(img)
	∇x = convolve(img_brightness, Sx)
	∇y = convolve(img_brightness, Sy)
	hbox(show_colored_array(∇x), show_colored_array(∇y))
	end

	# ╔═╡ d6a268c0-eff4-11ea-2c9e-bfef19c7f540
	begin
	edged = edgeness(img)
	# hbox(img, pencil(edged))
	hbox(img, Gray.(edgeness(img)) / maximum(abs.(edged)))
	end

	# ╔═╡ 552fb92e-ef05-11ea-0a79-dd7a6760089a
	hbox(mark_path(img, path), mark_path(show_colored_array(least_e), path))

	# ╔═╡ dfd03c4e-f06c-11ea-1e2a-89233a675138
	let
	hbox(mark_path(img, path), mark_path(pencil(e), path));
	end

	# ╔═╡ ca4a87e8-eff8-11ea-3d57-01dfa34ff723
	let
	# least energy path of them all:
	_, k = findmin(least_e[1, :])
	path = get_seam_at(dirs, k)
	hbox(
	mark_path(img, path),
	mark_path(show_colored_array(least_e), path)
	)
	end

	# ╔═╡ fa6a2152-ef0f-11ea-0e67-0d1a6599e779
	hbox(img, marked_carved[n], sy=size(img))

	# ╔═╡ 71b16dbe-f08b-11ea-2343-5f1583074029
	vbox(x,y, gap=16) = hbox(x', y')'

	# ╔═╡ ddac52ea-f148-11ea-2860-21cff4c867e6
	let
	∇y = convolve(brightness.(img), Sy)
	∇x = convolve(brightness.(img), Sx)
	# zoom in on the clock
	vbox(
	hbox(img[300:end, 1:300], img[300:end, 1:300]),
	hbox(show_colored_array.((∇x[300:end, 1:300], ∇y[300:end, 1:300]))...)
	)
	end

	# ╔═╡ 15d1e5dc-ef2f-11ea-093a-417108bcd495
	[size(img) size(carved[n])]

	# ╔═╡ 7e8084f4-f64f-11ea-322a-95f73f207421
	canvas

	# ╔═╡ 01d98866-f5cc-11ea-1010-57120dca4270
	begin
	mask = copy(img)
	mask[canvas[2]:(canvas[2]+canvas[4]),canvas[1]:(canvas[1]+canvas[3])] .= 0
	mask
	end

	# ╔═╡ Cell order:
	# ╟─8adfb3dc-f64f-11ea-3ee1-15e9bf47c49b
	# ╟─877df834-f078-11ea-303b-e98273ef98a4
	# ╟─0316b94c-eef6-11ea-19bc-dbc959901bb5
	# ╟─cb335074-eef7-11ea-24e8-c39a325166a1
	# ╟─bf750d0e-f35c-11ea-0245-713584583fcf
	# ╠═90f44be8-f35c-11ea-2fc6-c361fd4966af
	# ╟─d2ae6dd2-eef9-11ea-02df-255ec3b46a36
	# ╠═8ded023c-f35c-11ea-317c-11f5d1b67998
	# ╟─0b6010a8-eef6-11ea-3ad6-c1f10e30a413
	# ╠═fc1c43cc-eef6-11ea-0fc4-a90ac4336964
	# ╟─82c0d0c8-efec-11ea-1bb9-83134ecb877e
	# ╠═da726954-eff0-11ea-21d4-a7f4ae4a6b09
	# ╠═da39c824-eff0-11ea-375b-1b6c6e186182
	# ╠═074a58be-f146-11ea-382c-b7ae6c44bf75
	# ╠═abf6944e-f066-11ea-18e2-0b92606dab85
	# ╠═44192a40-eff2-11ea-0ec7-05cdadb0c29a
	# ╟─ac8d6902-f069-11ea-0f1d-9b0fa706d769
	# ╠═ddac52ea-f148-11ea-2860-21cff4c867e6
	# ╠═6f7bd064-eff4-11ea-0260-f71aa7f4f0e5
	# ╟─d6a268c0-eff4-11ea-2c9e-bfef19c7f540
	# ╟─172c7612-efee-11ea-077a-5d5c6e2505a4
	# ╟─fcf46120-efec-11ea-06b9-45f470899cb2
	# ╟─dec62538-efee-11ea-1e03-0b801e61e91c
	# ╟─f8283a0e-eff4-11ea-23d3-9f1ced1bafb4
	# ╟─025e2c94-eefb-11ea-12cb-f56f34886334
	# ╠═acc1ee8c-eef9-11ea-01ac-9b9e9c4167b3
	# ╠═8b204a2a-eff6-11ea-25b0-13f230037ee1
	# ╠═84d3afe4-eefe-11ea-1e31-bf3b2af4aecd
	# ╠═b507480a-ef01-11ea-21c4-63d19fac19ab
	# ╟─7d8b20a2-ef03-11ea-1c9e-fdf49a397619
	# ╠═f690b06a-ef31-11ea-003b-4f2b2f82a9c3
	# ╠═977b6b98-ef03-11ea-0176-551fc29729ab
	# ╠═9abbb158-ef03-11ea-39df-a3e8aa792c50
	# ╠═772a4d68-ef04-11ea-366a-f7ae9e1634f6
	# ╠═14f72976-ef05-11ea-2ad5-9f0914f9cf58
	# ╠═cf9a9124-ef04-11ea-14a4-abf930edc7cc
	# ╠═552fb92e-ef05-11ea-0a79-dd7a6760089a
	# ╠═081a98cc-f06e-11ea-3664-7ba51d4fd153
	# ╠═237647e8-f06d-11ea-3c7e-2da57e08bebc
	# ╠═dfd03c4e-f06c-11ea-1e2a-89233a675138
	# ╠═ca4a87e8-eff8-11ea-3d57-01dfa34ff723
	# ╠═4f23bc54-ef0f-11ea-06a9-35ca3ece421e
	# ╠═b401f398-ef0f-11ea-38fe-012b7bc8a4fa
	# ╠═b1b6b7fc-f153-11ea-224a-2578e8298775
	# ╠═2eb459d4-ef36-11ea-1f74-b53ffec7a1ed
	# ╟─e2cba094-f5fd-11ea-096d-37fe5fec7e8f
	# ╟─dc1bfcf8-f5fd-11ea-098d-b12fd21bb9df
	# ╠═7038abe4-ef36-11ea-11a5-75e57ab51032
	# ╟─2d6c6820-ef2d-11ea-1704-49bb5188cfcc
	# ╠═fa6a2152-ef0f-11ea-0e67-0d1a6599e779
	# ╟─71b16dbe-f08b-11ea-2343-5f1583074029
	# ╟─1fd26a60-f089-11ea-1f56-bb6eba7d9651
	# ╠═15d1e5dc-ef2f-11ea-093a-417108bcd495
	# ╠═7e8084f4-f64f-11ea-322a-95f73f207421
	# ╠═01d98866-f5cc-11ea-1010-57120dca4270