homework 2, version 1
Submission by: Jazzy Doe (jazz@mit.edu)
Homework 2 - seam carving
18.S191, fall 2020
This notebook contains built-in, live answer checks! In some exercises you will see a coloured box, which runs a test case on your code, and provides feedback based on the result. Simply edit the code, run it, and the check runs again.
For MIT students: there will also be some additional (secret) test cases that will be run as part of the grading process, and we will look at your notebook and write comments.
Feel free to ask questions!
"Jazzy Doe"
"jazz"
Let's create a package environment:
Activating new project at `/tmp/jl_Fyn05Z`
Updating registry at `~/.julia/registries/General.toml` Resolving package versions... Installed StringDistances ─ v0.11.3 Installed TestImages ────── v1.9.0 Updating `/tmp/jl_Fyn05Z/Project.toml` [6e4b80f9] + BenchmarkTools v1.6.0 [a81c6b42] + Compose v0.9.6 [6a3955dd] + ImageFiltering v0.7.10 [6218d12a] + ImageMagick v1.4.2 [916415d5] + Images v0.26.2 [7f904dfe] + PlutoUI v0.7.64 [5e47fb64] + TestImages v1.9.0 [10745b16] + Statistics Updating `/tmp/jl_Fyn05Z/Manifest.toml` [621f4979] + AbstractFFTs v1.5.0 [6e696c72] + AbstractPlutoDingetjes v1.3.2 [79e6a3ab] + Adapt v3.7.2 [66dad0bd] + AliasTables v1.1.3 [ec485272] + ArnoldiMethod v0.4.0 [4fba245c] + ArrayInterface v7.5.1 [13072b0f] + AxisAlgorithms v1.1.0 [39de3d68] + AxisArrays v0.4.7 [6e4b80f9] + BenchmarkTools v1.6.0 [62783981] + BitTwiddlingConvenienceFunctions v0.1.6 [fa961155] + CEnum v0.5.0 [2a0fbf3d] + CPUSummary v0.2.6 [aafaddc9] + CatIndices v0.2.2 [d360d2e6] + ChainRulesCore v1.25.1 [9e997f8a] + ChangesOfVariables v0.1.10 [fb6a15b2] + CloseOpenIntervals v0.1.13 [aaaa29a8] + Clustering v0.15.8 [35d6a980] + ColorSchemes v3.29.0 [3da002f7] + ColorTypes v0.12.1 [c3611d14] + ColorVectorSpace v0.11.0 [5ae59095] + Colors v0.13.1 [bbf7d656] + CommonSubexpressions v0.3.1 [34da2185] + Compat v4.16.0 [a81c6b42] + Compose v0.9.6 [ed09eef8] + ComputationalResources v0.3.2 [187b0558] + ConstructionBase v1.5.8 [150eb455] + CoordinateTransformations v0.6.3 [adafc99b] + CpuId v0.3.1 [dc8bdbbb] + CustomUnitRanges v1.0.2 [9a962f9c] + DataAPI v1.16.0 [864edb3b] + DataStructures v0.18.22 [163ba53b] + DiffResults v1.1.0 [b552c78f] + DiffRules v1.15.1 [b4f34e82] + Distances v0.10.12 [ffbed154] + DocStringExtensions v0.9.5 [4f61f5a4] + FFTViews v0.3.2 [7a1cc6ca] + FFTW v1.9.0 [5789e2e9] + FileIO v1.17.0 [53c48c17] + FixedPointNumbers v0.8.5 [f6369f11] + ForwardDiff v1.0.1 [a2bd30eb] + Graphics v1.1.3 [86223c79] + Graphs v1.12.1 [2c695a8d] + HistogramThresholding v0.3.1 [3e5b6fbb] + HostCPUFeatures v0.1.17 [47d2ed2b] + Hyperscript v0.0.5 [ac1192a8] + HypertextLiteral v0.9.5 [b5f81e59] + IOCapture v0.2.5 [615f187c] + IfElse v0.1.1 [2803e5a7] + ImageAxes v0.6.12 [c817782e] + ImageBase v0.1.7 [cbc4b850] + ImageBinarization v0.3.1 [f332f351] + ImageContrastAdjustment v0.3.12 [a09fc81d] + ImageCore v0.10.5 [89d5987c] + ImageCorners v0.1.3 [51556ac3] + ImageDistances v0.2.17 [6a3955dd] + ImageFiltering v0.7.10 [82e4d734] + ImageIO v0.6.9 [6218d12a] + ImageMagick v1.4.2 [bc367c6b] + ImageMetadata v0.9.10 [787d08f9] + ImageMorphology v0.4.6 [2996bd0c] + ImageQualityIndexes v0.3.7 [80713f31] + ImageSegmentation v1.9.0 [4e3cecfd] + ImageShow v0.3.8 [02fcd773] + ImageTransformations v0.10.2 [916415d5] + Images v0.26.2 [9b13fd28] + IndirectArrays v1.0.0 [d25df0c9] + Inflate v0.1.5 [1d092043] + IntegralArrays v0.1.6 [a98d9a8b] + Interpolations v0.15.1 [8197267c] + IntervalSets v0.7.11 [3587e190] + InverseFunctions v0.1.17 [92d709cd] + IrrationalConstants v0.2.4 [c8e1da08] + IterTools v1.4.0 [033835bb] + JLD2 v0.5.12 [692b3bcd] + JLLWrappers v1.7.0 [682c06a0] + JSON v0.21.4 [b835a17e] + JpegTurbo v0.1.6 [10f19ff3] + LayoutPointers v0.1.17 [8cdb02fc] + LazyModules v0.3.1 [2ab3a3ac] + LogExpFunctions v0.3.28 [bdcacae8] + LoopVectorization v0.12.172 [6c6e2e6c] + MIMEs v1.1.0 [1914dd2f] + MacroTools v0.5.16 [d125e4d3] + ManualMemory v0.1.8 [dbb5928d] + MappedArrays v0.4.2 [442fdcdd] + Measures v0.3.2 [626554b9] + MetaGraphs v0.8.0 [e1d29d7a] + Missings v1.2.0 [e94cdb99] + MosaicViews v0.3.4 [77ba4419] + NaNMath v1.0.3 [b8a86587] + NearestNeighbors v0.4.21 [f09324ee] + Netpbm v1.1.1 [6fe1bfb0] + OffsetArrays v1.17.0 [52e1d378] + OpenEXR v0.3.3 [bac558e1] + OrderedCollections v1.8.1 [f57f5aa1] + PNGFiles v0.4.4 [5432bcbf] + PaddedViews v0.5.12 [d96e819e] + Parameters v0.12.3 [69de0a69] + Parsers v2.8.3 [eebad327] + PkgVersion v0.3.3 [7f904dfe] + PlutoUI v0.7.64 [1d0040c9] + PolyesterWeave v0.2.2 [f27b6e38] + Polynomials v4.0.19 [aea7be01] + PrecompileTools v1.2.1 [21216c6a] + Preferences v1.4.3 [92933f4c] + ProgressMeter v1.10.4 [43287f4e] + PtrArrays v1.3.0 [4b34888f] + QOI v1.0.1 [94ee1d12] + Quaternions v0.7.6 [b3c3ace0] + RangeArrays v0.3.2 [c84ed2f1] + Ratios v0.4.5 [c1ae055f] + RealDot v0.1.0 [3cdcf5f2] + RecipesBase v1.3.4 [189a3867] + Reexport v1.2.2 [dee08c22] + RegionTrees v0.3.2 [ae029012] + Requires v1.3.1 [6038ab10] + Rotations v1.7.1 [fdea26ae] + SIMD v3.7.1 [94e857df] + SIMDTypes v0.1.0 [476501e8] + SLEEFPirates v0.6.43 [efcf1570] + Setfield v1.1.2 [699a6c99] + SimpleTraits v0.9.4 [47aef6b3] + SimpleWeightedGraphs v1.5.0 [45858cf5] + Sixel v0.1.3 [a2af1166] + SortingAlgorithms v1.2.1 [276daf66] + SpecialFunctions v2.5.1 [cae243ae] + StackViews v0.1.2 [aedffcd0] + Static v0.8.9 [0d7ed370] + StaticArrayInterface v1.6.0 [90137ffa] + StaticArrays v1.9.13 [1e83bf80] + StaticArraysCore v1.4.3 [82ae8749] + StatsAPI v1.7.1 [2913bbd2] + StatsBase v0.34.4 [88034a9c] + StringDistances v0.11.3 [62fd8b95] + TensorCore v0.1.1 [5e47fb64] + TestImages v1.9.0 [8290d209] + ThreadingUtilities v0.5.5 [731e570b] + TiffImages v0.11.4 [06e1c1a7] + TiledIteration v0.5.0 [3bb67fe8] + TranscodingStreams v0.11.3 [410a4b4d] + Tricks v0.1.10 [5c2747f8] + URIs v1.5.2 [3a884ed6] + UnPack v1.0.2 [3d5dd08c] + VectorizationBase v0.21.71 [e3aaa7dc] + WebP v0.1.3 [efce3f68] + WoodburyMatrices v1.0.0 [f5851436] + FFTW_jll v3.3.11+0 [61579ee1] + Ghostscript_jll v9.55.0+4 [59f7168a] + Giflib_jll v5.2.3+0 [c73af94c] + ImageMagick_jll v7.1.1048+0 [905a6f67] + Imath_jll v3.1.11+0 [1d5cc7b8] + IntelOpenMP_jll v2025.0.4+0 [aacddb02] + JpegTurbo_jll v3.1.1+0 [88015f11] + LERC_jll v3.0.0+1 [7e76a0d4] + Libglvnd_jll v1.7.1+1 [89763e89] + Libtiff_jll v4.5.1+1 [d3a379c0] + LittleCMS_jll v2.16.0+0 [856f044c] + MKL_jll v2025.0.1+1 [18a262bb] + OpenEXR_jll v3.2.4+0 [643b3616] + OpenJpeg_jll v2.5.4+0 [efe28fd5] + OpenSpecFun_jll v0.5.6+0 [ffd25f8a] + XZ_jll v5.8.1+0 [4f6342f7] + Xorg_libX11_jll v1.8.12+0 [0c0b7dd1] + Xorg_libXau_jll v1.0.13+0 [a3789734] + Xorg_libXdmcp_jll v1.1.6+0 [1082639a] + Xorg_libXext_jll v1.3.7+0 [c7cfdc94] + Xorg_libxcb_jll v1.17.1+0 [c5fb5394] + Xorg_xtrans_jll v1.6.0+0 [3161d3a3] + Zstd_jll v1.5.7+1 [b53b4c65] + libpng_jll v1.6.49+0 [075b6546] + libsixel_jll v1.10.5+0 [c5f90fcd] + libwebp_jll v1.4.0+0 [1317d2d5] + oneTBB_jll v2022.0.0+0 [0dad84c5] + ArgTools [56f22d72] + Artifacts [2a0f44e3] + Base64 [ade2ca70] + Dates [8ba89e20] + Distributed [f43a241f] + Downloads [7b1f6079] + FileWatching [9fa8497b] + Future [b77e0a4c] + InteractiveUtils [4af54fe1] + LazyArtifacts [b27032c2] + LibCURL [76f85450] + LibGit2 [8f399da3] + Libdl [37e2e46d] + LinearAlgebra [56ddb016] + Logging [d6f4376e] + Markdown [a63ad114] + Mmap [ca575930] + NetworkOptions [44cfe95a] + Pkg [de0858da] + Printf [9abbd945] + Profile [3fa0cd96] + REPL [9a3f8284] + Random [ea8e919c] + SHA [9e88b42a] + Serialization [1a1011a3] + SharedArrays [6462fe0b] + Sockets [2f01184e] + SparseArrays [10745b16] + Statistics [4607b0f0] + SuiteSparse [fa267f1f] + TOML [a4e569a6] + Tar [8dfed614] + Test [cf7118a7] + UUIDs [4ec0a83e] + Unicode [e66e0078] + CompilerSupportLibraries_jll [deac9b47] + LibCURL_jll [29816b5a] + LibSSH2_jll [c8ffd9c3] + MbedTLS_jll [14a3606d] + MozillaCACerts_jll [4536629a] + OpenBLAS_jll [05823500] + OpenLibm_jll [83775a58] + Zlib_jll [8e850b90] + libblastrampoline_jll [8e850ede] + nghttp2_jll [3f19e933] + p7zip_jll Precompiling project... ✓ StringDistances ✓ TestImages 2 dependencies successfully precompiled in 2 seconds (178 already precompiled)
Empty reply from server while requesting http://www.museumsyndicate.com/images/1/2957.jpg
Here is what happened, the most recent locations are first:
- (::Downloads.var"#9#18"{IOStream, Base.DevNull, Nothing, Vector{Pair{String, String}}, Float64, Nothing, Bool, Nothing, Bool, String, Bool, Bool})
(easy::Downloads.Curl.Easy) from Downloads.jl:387 - with_handle
(f::Downloads.var"#9#18"{IOStream, Base.DevNull, Nothing, Vector{Pair{String, String}}, Float64, Nothing, Bool, Nothing, Bool, String, Bool, Bool}, handle::Downloads.Curl.Easy) from Curl.jl:88 - anonymous functionfrom Downloads.jl:328
- arg_write
(f::Downloads.var"#8#17"{Base.DevNull, Nothing, Vector{Pair{String, String}}, Float64, Nothing, Bool, Nothing, Bool, String, Bool, Bool}, arg::IOStream) from ArgTools.jl:112 - anonymous functionfrom Downloads.jl:327
- arg_readfrom ArgTools.jl:61
- request
(url::String; input::Nothing, output::IOStream, method::Nothing, headers::Vector{Pair{String, String}}, timeout::Float64, progress::Nothing, verbose::Bool, debug::Nothing, throw::Bool, downloader::Nothing) from Downloads.jl:326 - anonymous functionfrom Downloads.jl:231
- arg_write
(f::Downloads.var"#3#4"{Nothing, Vector{Pair{String, String}}, Float64, Nothing, Bool, Nothing, Nothing, String}, arg::Nothing) from ArgTools.jl:101 - #download#2from Downloads.jl:230
- download
(url::String, output::Nothing) from Downloads.jl:230 - #invokelatest#2from essentials.jl:716
- invokelatestfrom essentials.jl:714
- do_downloadfrom download.jl:24
- downloadfrom download.jl:20
- from This cell: line 3
#img = load(download("https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/Hilma_af_Klint_-_Group_IX_SUW%2C_The_Swan_No._1_%2813947%29.jpg/477px-Hilma_af_Klint_-_Group_IX_SUW%2C_The_Swan_No._1_%2813947%29.jpg"))img = load(download("http://www.museumsyndicate.com/images/1/2957.jpg"))
Arrays: Slices and views
In the lecture (included below) we learned about what array views are. In this exercise we will add to that understanding and look at an important use of views: to reduce the amount of memory allocations when reading sub-sequences within an array.
We will use the BenchmarkTools package to emperically understand the effects of using views.
Shrinking an array
Below is a function called remove_in_each_row(img, pixels). It takes a matrix img and a vector of integers, pixels, and shrinks the image by 1 pixel in width by removing the element img[i, pixels[i]] in every row. This function is one of the building blocks of the Image Seam algorithm we saw in the lecture.
Read it and convince yourself that it is correct.
remove_in_each_row (generic function with 1 method)Let's use it to remove the pixels on the diagonal. These are the image dimensions before and after doing so:
Another cell defining img contains errors.
Exercise 1 - Making it efficient
We can use the @benchmark macro from the BenchmarkTools.jl package to benchmark fragments of Julia code.
@benchmark takes an expression and runs it a number of times to obtain statistics about the run time and memory allocation. We generally take the minimum time as the most stable measurement of performance (for reasons discussed in the paper on BenchmarkTools)
First, as an example, let's benchmark the remove_in_each_row function we defined above by passing in our image and a some indices to remove.
Another cell defining img contains errors.
Another cell defining img contains errors.
Exercise 1.1
vcat(x, y) is used in julia to concatenate two arrays vertically. This actually creates a new array of size length(x) + length(y) and copies x and y into it. We use it in remove_in_each_row to create rows which have one pixel less.
While using vcat might make it easy to write the first version of our function, it's strictly not necessary.
👉 In remove_in_each_row_no_vcat below, figure out a way to avoid the use of vcat and modify the function to avoid it.
remove_in_each_row_no_vcat (generic function with 1 method)Another cell defining img contains errors.
If you did it correctly, you should see that this benchmark shows the function running faster! And "memory estimate" should also show a smaller number, and so should "allocs estimate" which is the number of allocations done per call.
Exercise 1.2
👉 How many estimated allocations did this optimization reduce, and how can you explain most of them?
<Your answer here>
Exercise 1.3 - view-based optimization
👉 In the below remove_in_each_row_views function, implement the same optimization to remove vcat and use @view or @views to avoid creating copies or slices of the img array.
Pluto will automatically time your change with @benchmark below.
remove_in_each_row_views (generic function with 1 method)Another cell defining img contains errors.
Final tally:
Another cell defining img contains errors.
🙋 Run the cell above again to see the latest results!
Exercise 1.4
Nice! If you did your optimizations right, you should be able to get down the etimated allocations to a single digit number!
👉 How many allocations were avoided by adding the @view optimization over the vcat optimization? Why is this?
<your answer here>
Exercise 2 - Brightness and Energy
First, we will define a brightness function for a pixel (a color) as the mean of the red, green and blue values.
You should call this function whenever the problem set asks you to deal with brightness of a pixel.
brightness (generic function with 1 method)Another cell defining img contains errors.
In the previous problem set, we computed wrote code to compute the convolution of an image with a kernel. Here we will use the implementation of the same from the Julia package ImageFiltering.jl. Convolution is called imfilter in this package ("filter" is a term used in the signal processing world for convolution, and other operations that are like convolution.)
imfilter takes a
convolve (generic function with 1 method)float_to_color (generic function with 1 method)Another cell defining img contains errors.
finally we define the energy function which takes the gradients along x and y directions and computes the norm
energy (generic function with 1 method)removing 1 columns
Exercise 2: Building up to dynamic programming
In this exercise, we will use the image resizing example computational problem of Seam carving. We will think through all the "gut reaction" solutions, and then finally end up with the dynamic programming solution that we saw in the lecture.
In the process we will understand the performance and accuracy of each iteration of our solution.
How to implement the solutions:
For every variation of the algorithm, your job is to write a function which takes a matrix of energies, and an index for a pixel on the first row, and computes a "seam" starting at that pixel.
The function should return a vector of as many integers as there are rows in the input matrix where each number points out a pixel to delete from the corresponding row. (it acts as the input to remove_in_each_row).
2.1 The greedy approach
👉 Implement the greedy approach discussed in the lecture,
greedy_seam (generic function with 1 method)2.2 Exhaustive search with recursion
A common trope in algorithm design is the possibility of solving a problem as the combination of solutions to subproblems.
An analogy can be drawn to the process of mathematical induction in mathematics. And as with mathematical induction there are parts to constructing such a recursive algorithm:
Defining a base case
Defining an induction step, i.e. finding a solution to the problem as a combination of solutions to smaller problems.
2.2.1
Define least_energy function which returns
the lowest possible total energy for a seam starting at the pixel at (i, j).
the column to jump to on the next move (in row i+1),
which is one of j-1,j or j+1, up to boundary conditions.
return these two values in a tuple.
You can call the least_energy function recursively within itself to obtain the least energy of the adjacent cells and add the energy at the current cell to get the total energy.
least_energy (generic function with 1 method)2.2.2
Now use the least_energy function you defined above to define recursive_seam function which takes the energies matrix and a starting pixel, and computes the seam with the lowest energy from that starting pixel.
This will give you the method used in the lecture to perform exhaustive search of all possible paths.
recursive_seam (generic function with 1 method)2.2.3
State clearly why this algorithm does an exhaustive search of all possible paths.
How many such paths are there in an image of size
m×n?
<your answer here>
2.3 Memoization
Memoization is the name given to the technique of storing results to expensive function calls that will be accessed more than once.
As stated in the video, a the function least_energy is called with the same number of arguments. In fact, we call it on the order of
Lets implement memoization on this function with first a dictionary for storage and then a matrix.
2.3.1 Dictionary as storage
First we will start a memoized version of
memoized_seam (generic function with 2 methods)2.3.2 Matrix as storage
While the dictionary works just as well, and more generally if we were stor
matrix_memoized_seam (generic function with 2 methods)2.4 Memoization without recursion – final solution
Now it's easy to see that the above algorithm is equivalent to one that populates the memory matrix in a for loop.
2.4.1
Write a function which takes the energies and returns the least energy matrix which has the least possible seam energy for each pixel. This was shown in the lecture, but attempt to write it on your own.
least_energy_matrix (generic function with 1 method)2.4.2
Write a function which when given the matrix returned by least_energy_matrix and a starting pixel (on the first row), computes the least energy seam from that pixel.
seam_from_precomputed_least_energy (generic function with 1 method)shrink_n (generic function with 1 method)write a thing that shows them the result – with a slider to repeatedly apply it.
write a thing that plots the time taken
decimate (generic function with 1 method)Oops!
Before you submit, remember to fill in your name and kerberos ID at the top of this notebook!
hint (generic function with 1 method)almost (generic function with 1 method)still_missing (generic function with 2 methods)keep_working (generic function with 2 methods)Great!
Yay ❤
Great! 🎉
Well done!
Keep it up!
Good job!
Awesome!
You got the right answer!
Let's move on to the next section.
correct (generic function with 2 methods)not_defined (generic function with 1 method)