5

The 2nd problem in IOI 2013 states:

You have an Art History exam approaching, but you have been paying more attention to informatics at school than to your art classes! You will need to write a program to take the exam for you.

The exam will consist of several paintings. Each painting is an example of one of four distinctive styles, numbered 1, 2, 3 and 4. Style 1 contains neoplastic modern art. Style 2 contains impressionist landscapes. Style 3 contains expressionist action paintings. Style 4 contains colour field paintings.

Your task is, given a digital image of a painting, to determine which style the painting belongs to.

The image will be given as an H×W grid of pixels. The rows of the image are numbered 0, …, (H ­ 1) from top to bottom, and the columns are numbered 0, …, W ­ 1 from left to right. The pixels are described using two­dimensional arrays R , G and B , which give the amount of red, green and blue respectively in each pixel of the image. These amounts range from 0 (no red, green or blue) to 255 (the maximum amount of red, green or blue).

Implementation You should submit a file that implements the function style(), as follows:

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]);

This function should determine the style of the image. Parameters are:

  • H: The number of rows of pixels in the image.
  • W: The number of columns of pixels in the image.
  • R: A two­dimensional array of size H×W , giving the amount of red in each pixel of the image.
  • G: A two­dimensional array of size H×W , giving the amount of green in each pixel of the image.
  • B: A two­dimensional array of size H×W , giving the amount of blue in each pixel of the image.

Example pictures are in the problem PDF

I do not want a readymade program. A hint or two to get me started would be nice, as I am clueless about this might be solved.

Community
  • 1
  • 1
Soham Chowdhury
  • 2,125
  • 2
  • 18
  • 29

2 Answers2

15

Since you are provided the image data in RGB format, first prepare a copy of the same image data in YUV. This is essential as some of the image features are easily identified patterns in the Luma(Y) and Chroma(U,V) maps.

Based on the samples provided, here are some of the salient features of each "style" of art :

Style1 - Neoplastic modern art

Neoplastic modern art

  • Zero graininess - Check for large areas with uniform Luma(Y)
  • Black pixels at edges of the areas(transition between different chroma).

Style2 - Impressionist landscapes

Impressionist landscapes

  • High graininess - Check for high entropy (salt-n-pepper-noise like) patterns in Luma(Y).
  • Pre-dominantly green - High values in green channel.
    Greenavg >> Redavg
    Greenavg >> Blueavg

Style3 - Expressionist action paintings

Expressionist action paintings

Style4 - Color field paintings

Color field paintings

  • Zero graininess - Check for large areas with uniform Luma(Y)
  • NO black(or near black) pixels at the transition between different chroma.

As long as the input image belongs to one of these classes you should have no trouble in classification by running the image data through functions that are implemented to identify the above features.

Basically it boils down to the following code-flow :

  • Image has uniform luma?
    • (If Yes) Image has black pixels at chroma transitions?
      • (If Yes) Style1
      • (If No) Style4
    • (If No) Image is green-ish?
      • (If Yes) Style2
      • (If No) Style3
TheCodeArtist
  • 21,479
  • 4
  • 69
  • 130
  • the sampling can be important too, I mean how you "quantify" the YUV parameters from a given RGB area. That can be tricky. – user2485710 Aug 02 '13 at 09:23
  • @user2485710 You are right. But since we are NOT interested in compression of any sorts, we will not be sub-sampling chroma. One can use a simple formula as shown [here](http://stackoverflow.com/a/1737741/319204). Checkout this short article with [C++ code](http://www.codeproject.com/Articles/402391/RGB-to-YUV-conversion-with-different-chroma-sampli) that demonstrates relative difference and visual artifacts introduced by chroma sub-sampling. – TheCodeArtist Aug 02 '13 at 09:28
  • The reasoning behind the code-flow is flawed. Expressionist action paintings could be green, too. – Daniel Daranas Aug 29 '13 at 15:24
  • 1
    @DanielDaranas Agreed. The answer is simply based on the sample images provided in the problem statement. The OP explicitly requested a hint to approach the problem of classifying the images in a reasonably short time-frame. With additional sample images of known "style", the logic can (and needs to) be tuned. – TheCodeArtist Aug 29 '13 at 15:51
0

Maybe you can do a first approach using colors and shapes... In neo plastic modern it is likely that there will be only a few number of colors, occupying geometrical areas as in the colour field paintings.

This might gives you a way to differenciate styles 1 and 4 from styles 2 and 3.

In styles 1 and 4 you have large areas with the same color, but in style 4 the color is rarely a solid color but brush strokes of shades of the color.

Anyway you should look into the specialities of each styles, which are the usual colors and methods and then try to make your function "see" it.

Marc
  • 2,631
  • 1
  • 12
  • 13