# Boxcam

# 1 Example

Input:

Output (quality 10, 10 seeds, 12.5 seconds calculation):

Output (quality 24, 10 seeds, 12.5 minutes calculation):

# 2 Implementation

I used the C programming language with summed-area table data structure to accelerate computations.

Vector PDFs are generated using bytestring concatenation, with zlib for /FlateDecode compression. After each rectangle is drawn, a PDF is generated in memory, the process stops if the PDF exceeds 4096 bytes. The last PDF not exceeding 4096 bytes is emmited.

Download: boxcam.c.

# 3 Efficiency

Naive search over all rectangles would cost $O(w^3×h^3)$. Summed area tables, costing $O(w×h)$ to construct, bring the costs down to $O(w^2×h^2)$. A combined search with column tables to accelerate Kadane’s algorithm might cost $O(w×h×min(w, h))$. Randomized search is not guaranteed to find the optimum solution, but costs $O(w×h + k)$ including summed area table construction.

# 4 Maths

First transform input from sRGB to linear RGB (approximately: square the sRGB channel values).

Then work in linear RGB.

Last transform back to sRGB for output (approximately: square root the linear RGB channel values).

In linear RGB, score each rectangle by difference between sum of squared differences between target X and canvas Y before and after the rectangle is drawn. Most improving rectangle wins.

Best colour for the rectangle is just the mean of the region in the target (can be shown by minimizing a quadratic).

Then ignoring parts that are the same for all rectangles the score is:

$$s = 2 \sum XY - \sum Y^2 - \left(\sum X\right)^2 / \sum 1$$

where each sum is over the rectangle. Lowest score wins.