Domino Art

[venaturum]

Why this Mod?

As seen in this article

Not everyone will have a but everyone has a picture. If you have a picture, you can approximate it with dominoes

What will the API be?

Very small. Something like:

image = Image.from_file(...)
image.set(width=40)
image.preview()

problem = Problem(image)
domino_placements = problem.make(max_domino_sets = 10)

draw_solution(domino_placements)

It would ideally use matplotlib (for easy conversion of arrays to image) and Pillow (which is also a dependency of matplotlib)

• Riley

[simonbowly]

Sounds fun! Not sure I follow the reason for the Problem() -> Problem.make() split API though? Just a single function make_domino_art(image, max_domino_sets=n) would make more sense I think.

What would the returned result be? Ideally we would not depend on matplotlib & pillow by default as these are far from the only image handling libraries out there. Maybe at first define the API with numpy arrays as the I/O format, and show how to ingest various image types in the docs?

[venaturum]

Not sure I follow the reason for the Problem() -> Problem.make() split API though? Just a single function make_domino_art(image, max_domino_sets=n) would make more sense I think.

I can implement a function like so

def make_domino_art(image, max_domino_sets=n):
    return Problem(image).make(max_domino_sets=n)

but ideally I'd still allow users access to the Problem class. When a Problem object is instantiated there is a bit of work to do. For a 50 x 50 tile image with double-9 dominoes for example there are 270k domino/position combinations, and an objective coefficient must be calculated for each by computing the minimum of two squares. The whole thing takes about 8s on my machine - longer than the actual Gurobi solve time. This setup is invariant to the number of domino sets, so the above function would create unnecessary recomputation when users play around with the number of domino sets - which affects the quality of the image. A few options:

i) keep the API as initially proposed
ii) implement the function above in addition
iii) incorporate the Image class functionality into the Problem class so the user only sees one class

What would the returned result be?

A dataclass with some basic stats about the solution, and an assignment of dominoes to positions. This can be then fed to a drawing function.

Ideally we would not depend on matplotlib & pillow by default as these are far from the only image handling libraries out there.

We're going to need conversion between images and numpy arrays on the front but also the back. Image -> array for reading, and array -> image for drawing solution. We also need the image library to resize and "posterize" for us. I think these details are best hid from the user, which means anchoring ourselves to some library - I don't mind which though. We could always include matplotlib and pillow as optional dependencies which get installed with
pip install gurobi-optimods[domino]
I could also publish the image <-> array functionality as a separate package with optimods as a dependency if that works?

[simonbowly]

i) keep the API as initially proposed

Ok, makes sense to have the two step process in that situation.

We're going to need conversion between images and numpy arrays on the front but also the back.

I'm suggesting at a minimum the API should accept a numpy array as a (grayscale I presume?) bitmap. Then you aren't tied to a particular image format and the user can do e.g.:

# using pillow
from PIL import Image
image = Image.open("photo.jpg")
problem = Problem(np.array(image.convert("L"))
domino_placements = problem.make(max_domino_sets = 10)

# using opencv-python
import cv2
bitmap = cv2.imread("photo.jpg", cv2.IMREAD_GRAYSCALE)
problem = Problem(bitmap)
domino_placements = problem.make(max_domino_sets = 10)

If you also want to handle a pillow Image object natively, that can also be handled internally in a similar way to how networkx graphs in the bipartite matching code. Actually pillow seems to be unique in handling images via a wrapped object. opencv2, scipy, skimage & mahotas all have functional APIs and handle images as numpy arrays. So I'd argue the API is best kept general here, maybe with pillow as an optionally handled special case.

The same maybe true of the backend: matplotlib.imshow also expects a numpy array.

[venaturum]

Cool, I think I know what I need to do. Currently the pillow and matplotlib library is all under the hood - I should have renamed the Image class in my example to make it clear, it is a class that relies on pillow and matplotlib, but the user is never exposed to these libraries. Still thinking of rolling all functionality into one class that is presented to the user then just delegating methods under the hood, and handling the potential absence of matplotlib with exceptions à la
pandas. Any objection to adding

develop = [
    "pillow",
    "matplotlib",
]

to project.optional-dependencies, and python -m pip install -e .[develop] in order to facilitate testing?

[simonbowly]

Sure - although the CI jobs will not know to install the extras, so the jobs will always fail. While hacking away on your fork, just put pillow and matplotlib as regular dependencies to make sure they are installed, we can adjust later.

[venaturum]

Too easy, I'll look to sort it over the weekend.