This is a take home test.
The goal of this task is to build a small image processing library that fills holes in images, along with a small command line utility that uses that library, and answer aΒ few questions.
See detailed assignment in Hole Filling 3 - Interview Exercise.pdf.
- Solve the assignment.
- Demonstrate the ultra-modular design of decoupled composable components.
To see in action change your current console directory to fill-hole
Swift Package folder and run the following command
$ swift run fill-hole -h
to see fill-hole
command line description and arguments:
OVERVIEW: Image Hole Filler.
`fill-hole` is a command line utility that fills the hole in the image.
Provide URLs for the source image and hole (mask), parameters of the weight function `z` and `e`, and (optional) output
image file name.
USAGE: fill-hole <source> <mask> <z> <e> <connectivity> [<output-file>]
ARGUMENTS:
<source> Source image URL.
<mask> Hole (mask) image URL.
<z> `z` parameter of the weight function.
<e> `e` parameter of the weight function: small float value used to avoid division by zero.
<connectivity> Pixel connectivity type: 4 or 8.
<output-file> (Optional) name of output file without extension. The command only writes to the current
directory. (default: output)
OPTIONS:
-h, --help Show help information.
Output file name could be omitted, its extension, if provided, is ignored (for simplicity of v.001).
Run the following command:
$ swift run fill-hole <image url> <hole url> 2 0.001 4
Drag-n-drop image file instead of <image url>
, and mask (hole) file for <hole url>
.
If you miss any argument you'll see an error, for example:
Error: Missing expected argument '<connectivity>'
Help: <connectivity> Pixel connectivity type: 4 or 8.
Usage: fill-hole <source> <mask> <z> <e> <connectivity> [<output-file>]
See 'fill-hole --help' for more information.
URLs of the source, mask, and output would be printed when the command finishes successfully. Run ls
to list folder contents, including the output image:
$ ls
Package.resolved README.md Tests output.png
Package.swift Sources docs
Run open output.png
to open it.
The solution is implemented using Swift Package.
To simplify reasoning, have clear responsibilities, and construct decoupled components, we divided the codebase into the following targets inside one Swift Package:
fill-hole
(executable target)FillHoleCommand
FillHoleLib
GrayscaleIOLib
FillHoleCommand
, FillHoleLib
, and GrayscaleIOLib
are accompanied by tests in their respective test targets.
Here is the top-level view of modules and dependencies:
Here is more detailed view with components:
-
Command line utility
fill-hole
is a simple thin executable wrapper for theFillHoleCommand
. -
FillHoleCommand
FillHoleCommand
accepts aninput image
file,hole
(mask) file, weight function parametersπ§
andΞ΅
, andconnectivity
type, fills the hole and writes the result to an output image file.It's implemented using Swift Argument Parser by Apple.
FillHoleCommand
as aParsableCommand
uses its default implementation of the static funcmain()
. To preserve the functionality and compatibility, there is no way of using constructor injection withFillHoleCommand
. As a compromise, we use implicit dependencies (Valuator
andRunner
) consideringFillHoleCommand
a composition layer, that wrapsValuator
andRunner
logic.Valuator
andRunner
use constructor injection with polymorphic interfaces, so we can easily swap their dependencies.The
FillHoleCommand
doesnβt support an arbitrary weight function, only the default one with configurable π§ and Ξ΅. -
FillHoleLib
FillHoleLib
is a module with algorithm for hole filling. Its two main components areHoleFiller
andBalance
.HoleFiller
is initialized withPixelConnectivity
andBalance
and has a function tofill
the hole in the image.Balance
holdsWeightFunc
, either arbitrary ordefault
weighting function1 / (||u - v||^z + Ξ΅),
where
Ξ΅ (epsilon)
is a small float value used to avoid division by zero, and||u - v||
denotes the euclidean distance betweenu
andv
. -
GrayscaleIOLib
This is not a generic file IO operations suite, but a very concrete case of loading grayscale images from files and saving such images using
ImageIO
, the performant API from Apple (CGImageSource
,CGImageDestination
).
- If there are π boundary pixels and π pixels inside the hole, whatβs the complexity of the algorithm that fills the hole, assuming that the hole and boundary were already found? Try to also express the complexity only in terms of π.
O(n * m)
O(n * βn)
- idea:n
is like the area of the hole, andm
is the perimeter, so O(m) β O(βn).
(a) Could you imagine the case where it would be
O(n * n)
?
- Yes, consider long thin rectangle - its perimeter would be
~O(n)
and overall complexity would beO(nΒ²)
.
- Describe an algorithm that approximates the result in π(π) to a high degree of accuracy. Bonus: implement the suggested algorithm in your library in addition to the algorithm described above.
We could change each hole pixel color to the average color of the boundary.
In this case, the complexity would be O(n + m)
, where m < n
, which is equivalent to O(n)
.
A more granular approach would be the following: divide the boundary into k sets of pixels, calculate average color and "average" coordinates for each set thus creating a set of pixels newBoundary
, and run the basic algorithm against the original hole and newBoundary.
Complexity:
- Creating newBoundary of
k
pixels from the original boundary ofm
pixels:m
- Filling the hole:
k * n
- Total
O(m) + O(k * n) β² O(n)
- Bonus (hard!): Describe and implement an algorithm that finds the exact solution in π(πππππ). In this section, feel free to use any algorithmic functionality provided by external libraries as needed.
In this case I would think about gradually shrinking boundary and hole:
// pixelConnectivity: PixelConnectivity is given
let neighborhood: (Pixel) -> [Pixel] = { pixel in
pixelConnectivity.neighbours(of: pixel)
}
// copy already found boundary: Boundary = Set<Pixel>
var boundary = boundary
// copy existing hole: Hole = Set<Pixel>
var hole = hole
while !hole.isEmpty {
let neighbours = boundary.map(neighborhood).reduce([], +))
// boundary shrinking inwards
let newBoundary = Set(neighbours).intersection(hole)
newBoundary.forEach { pixel in
// paint pixel using neighbours in boundary
// ...
}
hole = hole.subtract(newBoundary)
boundary = newBoundary
}
The upcoming macOS13
is able to work with async
commands, i.e. FillHoleCommand.main()
would be able to run asynchronously.