Author:

• Name: Ilya Kurdyukov
  Location: RU - Russian Federation (Russia)

To build:

    make

To use:

    ./prog

Try:

    # Take a selfie
    ./prog 1000 selfie.jpg output.jpg
    # Admire your portrait in cubist style

    # Also try:
    ./try.sh

Judges’ remarks:

This entry has reminded us of a winning entry back in the early 90s. Can you guess which one?

For a given image, try graphing the execution time relative to the number of rectangles. What is the complexity? Is it obvious from the source code?

Author’s remarks:

Usage

This program divides the image into a specified number of rectangles. This process is content aware, so the algorithm tries to match most of the information. However, it doesn’t find the best theoretically possible layout.

    ./prog 1000 input.jpg output.jpg

Building

You can build three versions, depending on the image format.

Default is JPEG version; if you have the libjpeg development package installed in your system, then make without arguments should do the right thing.

If you want to use libjpeg compiled from sources, then use the LIBJPEG define to specify the path to includes and the library. For example using libjpeg source version 9c:

    make prog LIBJPEG="-Ijpeg-9c jpeg-9c/libjpeg.a"

Use this command to build a PNG version (you need libpng):

    make prog_png LIBPNG="-lpng"

And the PPM version (no additional dependencies, can read raw/ASCII PPM, writes raw PPM):

    make prog_ppm

Building on macOS with MacPorts:

Thanks to Cody Boone Ferguson for this information!

First, make sure you have the compiler tools installed e.g. by:

    sudo xcode-select --install

Make sure you install MacPorts. Then do:

    sudo port install jpeg libpng ImageMagick

The program itself doesn’t need ImageMagick, install it only if you plan to make GIFs from the results using makegif.sh.

After that’s installed you need to run make with these options:

    make LDFLAGS="-I/opt/local/include -L/opt/local/lib"

Building on macOS with Homebrew

First, make sure you have the compiler tools installed e.g. by:

    sudo xcode-select --install

Make sure you install Homebrew.

Then:

    brew install libjpeg libpng
    eval "$(brew shellenv)"

You are now ready to compile this entry:

    make clobber all

Notes

Made this thing while experimenting with the idea of representing an image with rectangles (lossy compression). It’s not very good in that sense, but the results look funny, like a kind of cubism pixel art.

Do not use values above 50000, it’ll be slow.

To understand how this works, just try running with 1,2,3,4… number of rectangles. At each iteration, the rectangle with the biggest difference from the picture data is split (halves may have different size) horizontally or vertically to get the minimum difference.

You can use this command to make a GIF from output images (uses ImageMagick). For instance after running the command suggested by the judges:

    convert -delay 10 -dither none -loop 0 $(find . -maxdepth 1 -type f -name '*jpg' | sort -V) $(find . -maxdepth 1 -type f -name '*jpg' | sort -rV) +map out.gif

NOTE: the above is done in the try.sh script.

Also provided makegif.sh to aid with GIF creation.

Primary files

• prog.c - entry source code
• Makefile - entry Makefile
• prog.orig.c - original source code
• try.sh - script to try entry
• makegif.sh - script to form GIFs from the results
• prog.png.c - build a PNG version
• prog.ppm.c - build a PPM version
• sample.jpg - sample image input file

Secondary files

• 2020_kurdyukov2.tar.bz2 - download entry tarball
• README.md - markdown source for this web page
• .entry.json - entry summary and manifest in JSON
• .gitignore - list of files that should not be committed under git
• .path - directory path from top level directory
• index.html - this web page

Jump to: top