Отверстие № 1

Джо змея голодна.

Он ест картинки, по одному пикселю за раз.

Он действительно любит яркие пиксели.

Соревнование

Запрограммируйте Джо, чтобы он съел самые яркие пиксели, которые он может найти, учитывая, что он может двигаться только вверх, вниз, влево или вправо.

Характеристики

• Джо должен начать с верхнего левого пикселя изображения.
• Джо может двигаться только горизонтально или вертикально на 1 каждый ход
• У Джо достаточно времени, чтобы переместить 1/3 количества пикселей на картинке (на 1/3 столько же, сколько пикселей). Если количество пикселей не кратно 3, округлите до ближайшего целого числа.
• Джо может пересечь свой путь, хотя это считается как 0 яркости
• Яркость основана на сумме r, g и b, поэтому яркость rgb (0,0,0) равна 0, а максимальная яркость - rgb (255,255,255).

вход

Вы можете ввести изображение, как вам нравится.

Выход

• изображение, показывающее конечный результат вашей картинки (с черными пикселями).
• Количество съеденной яркости (укажите, какой диапазон в вашем ответе)

счет

Ваша программа будет оценена на:

• Средняя яркость пикселей, которые съедает Джо / Средняя яркость пикселей на картинке *

* Вы можете жестко закодировать это в своей программе

Ваш общий балл будет средним из баллов для следующих изображений:

Тестовые изображения:

http://upload.wikimedia.org/wikipedia/en/thumb/f/f4/The_Scream.jpg/800px-The_Scream.jpg

C ++, оценка: 1,42042 1,46766

По сути, это немного более сложная версия двух существующих решений: из четырех возможных ходов он выбирает тот, который максимизирует яркость. Однако вместо того, чтобы смотреть только на яркость целевого пикселя, он смотрит на взвешенную сумму яркости пикселей в окрестности целевого пикселя, где пиксели, расположенные ближе к цели, имеют больший вес.

РЕДАКТИРОВАТЬ: Использование нелинейной яркости в расчете окрестности немного улучшает оценку.

Компилировать с g++ joe.cpp -ojoe -std=c++11 -O3 -lcairo. Требуется Каир.

Беги с joe <image-file> [<radius>]. <image-file>является входным PNG-изображением. <radius>(необязательный аргумент) - радиус суммированной окрестности в пикселях (чем меньше, тем быстрее, чем больше (примерно), тем лучше). Выводится оценка и имя с именем out.<image-file>.

#include <cairo/cairo.h>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>

using namespace std;

int main(int argc, const char* argv[]) {
    auto* img = cairo_image_surface_create_from_png(argv[1]);
    int width = cairo_image_surface_get_width(img),
        height = cairo_image_surface_get_height(img),
        stride = cairo_image_surface_get_stride(img);
    unsigned char* data = cairo_image_surface_get_data(img);

    double* brightness = new double[width * height];
    double total_brightness = 0;
    for (int y = 0; y < height; ++y) {
        for (int x = 0; x < width; ++x) {
            const unsigned char* p = data + stride * y + 4 * x;
            total_brightness += brightness[y * width + x] = p[0] + p[1] + p[2];
        }
    }

    const int r = argc > 2 ? stoi(argv[2]) : 64, R = 2 * r + 1;
    double* weight = new double[R * R];
    for (int y = -r; y <= r; ++y) {
        for (int x = -r; x <= r; ++x)
            weight[R * (y + r) + (x + r)] = 1.0 / (x*x + y*y + 1);
    }

    auto neighborhood = [&] (int x, int y) {
        double b = 0;
        int x1 = max(x - r, 0), x2 = min(x + r, width - 1);
        int y1 = max(y - r, 0), y2 = min(y + r, height - 1);
        for (int v = y1; v <= y2; ++v) {
            const double *B = brightness + width * v + x1;
            const double *W = weight + R * (v - (y - r)) + (x1 - (x - r));
            for (int u = x1; u <= x2; ++u, ++B, ++W)
                b += (*W) * (*B) * (*B);
        }
        return b;
    };

    int n = (2 * width * height + 3) / 6;
    int x = 0, y = 0;
    double path_brightness = 0;
    int O[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int i = 0; i < n; ++i) {
        if (i % 1000 == 0) cerr << (200 * i + n) / (2 * n) << "%\r";

        path_brightness += brightness[width * y + x]; brightness[width * y + x] = 0;
        unsigned char* p = data + stride * y + 4 * x;
        p[0] = p[1] = 16 * i % 255; p[2] = 0;

        auto O_end = partition(begin(O), end(O), [&] (const int* o) {
            return x + o[0] >= 0 && x + o[0] < width &&
                   y + o[1] >= 0 && y + o[1] < height;
        });
        const int* o_max; double o_max_neighborhood = -1;
        for (auto o = O; o != O_end; ++o) {
            double o_neighborhood = neighborhood(x + (*o)[0], y + (*o)[1]);
            if (o_neighborhood > o_max_neighborhood)
                o_max = *o, o_max_neighborhood = o_neighborhood;
        }
        x += o_max[0]; y += o_max[1];
    }

    cout << (path_brightness * width * height) / (n * total_brightness) << endl;

    cairo_surface_write_to_png(img, (string("out.") + argv[1]).c_str());

    delete []brightness;
    delete []weight;
    cairo_surface_destroy(img);
}

Полученные результаты

Bridge    1.39945
Balls     1.77714
Scream    1.38349
Fractal   1.31727
Vortex    1.66493
Tornado   1.26366
-----------------
Average   1.46766

Больше глазных конфет

Python 3, оценка = 1,57

Сначала наша змея перемещается по изображению, создавая вертикальные линии на равном расстоянии друг от друга.

Мы можем расширить эту змею, взяв две точки рядом друг с другом на вертикальной линии и создав петлю, конечными точками которой являются они.

|      |
|  =>  +----+
|      +----+
|      |

Мы организуем точки в пары, и для каждой пары мы сохраняем размер и среднее значение яркости петли, которая дает наибольшую среднюю яркость.

На каждом шаге мы выбираем пару с наибольшим значением, расширяем ее цикл, чтобы достичь максимальной средней яркости на расширении, и вычисляем новый оптимальный размер цикла и значение яркости для пары.

Мы храним триплеты (value, size, point_pair) в структуре кучи, отсортированной по значению, чтобы мы могли удалить самый большой элемент (в O (1)) и эффективно добавить новый модифицированный (в O (log n)).

Мы останавливаемся, когда достигаем предела количества пикселей, и эта змея будет последней змеей.

Расстояние между вертикальными линиями мало влияет на результаты, поэтому был выбран постоянный пиксель в 40 пикселей.

Полученные результаты

swirl    1.33084397946
chaos    1.76585674741
fractal  1.49085737611
bridge   1.42603926741
balls    1.92235115238
scream   1.48603818637
----------------------
average  1.57033111819

Примечание: оригинальная картинка «Крик» была недоступна, поэтому я использовал другую картинку «Крик» с аналогичным разрешением.

Gif, показывающий процесс расширения змеи на изображении «вихря»:

Код берет одно (или более разделенное пробелами) имя файла (ов) из стандартного ввода и записывает полученные изображения змей в файлы png и печатает результаты в стандартный вывод.

from PIL import Image
import numpy as np
import heapq as hq

def upd_sp(p,st):
    vs,c=0,0
    mv,mp=-1,0
    for i in range(st,gap):
        if p[1]+i<h:
            vs+=v[p[0],p[1]+i]+v[p[0]+1,p[1]+i]
            c+=2
            if vs/c>mv:
                mv=vs/c
                mp=i
    return (-mv,mp)

mrl=[]
bf=input().split()

for bfe in bf:
    mr,mg=0,0    
    for gap in range(40,90,1500):

        im=Image.open(bfe)
        im_d=np.asarray(im).astype(int)

        v=im_d[:,:,0]+im_d[:,:,1]+im_d[:,:,2]

        w,h=v.shape

        fp=[]
        sp=[]
        x,y=0,0
        d=1

        go=True
        while go:
            if 0<=x+2*d<w:
                fp+=[(x,y)]
                fp+=[(x+d,y)]
                sp+=[(x-(d<0),y)]
                x+=2*d
                continue
            if y+gap<h:
                for k in range(gap):
                    fp+=[(x,y+k)]
                y+=gap
                d=-d
                continue
            go=False

        sh=[]
        px=im.load()

        pl=[]

        for p in fp:
            pl+=[v[p[0],p[1]]]
            px[p[1],p[0]]=(0,127,0)   

        for p in sp:
            mv,mp=upd_sp(p,1)
            if mv<=0:
                hq.heappush(sh,(mv,1,mp+1,p))

        empty=False
        pleft=h*w//3
        pleft-=len(fp)
        while pleft>gap*2 and not empty:

            if len(sh)>0:
                es,eb,ee,p=hq.heappop(sh)
            else:
                empty=True
            pleft-=(ee-eb)*2

            mv,mp=upd_sp(p,ee)
            if mv<=0:
                hq.heappush(sh,(mv,ee,mp+1,p))    

            for o in range(eb,ee):
                pl+=[v[p[0],p[1]+o]]
                pl+=[v[p[0]+1,p[1]+o]]
                px[p[1]+o,p[0]]=(0,127,0)   
                px[p[1]+o,p[0]+1]=(0,127,0)

        pl+=[0]*pleft

        sb=sum(pl)/len(pl)
        ob=np.sum(v)/(h*w)

        im.save(bfe[:-4]+'snaked.png')

        if sb/ob>mr:
            mr=sb/ob
            mg=gap

    print(bfe,mr)
    mrl+=[mr]

print(sum(mrl)/len(mrl))

Python 2 (оценка: 0,0797116)

Просто очень простой и наивный жадный алгоритм, чтобы заставить мяч двигаться.

#!/usr/bin/python

from PIL import Image

OFFSETS = [(-1, 0), (0, -1), (1, 0), (0, 1)]
def test_img(filename):
    img = Image.open(filename)

    joe, eaten = (0, 0), []
    img_w, img_h = img.size
    all_pixels = [
        sum(img.getpixel((x, y)))
        for x in xrange(img_w)
        for y in xrange(img_h)
    ]
    total_brightness = float(sum(all_pixels)) / len(all_pixels)

    for _ in xrange(0, (img_w*img_h)/3):
        max_offset, max_brightness = (0, 0), 0
        for o in OFFSETS:
            try:
                brightness = sum(img.getpixel((joe[0] + o[0], joe[1] + o[1])))
            except IndexError:
                brightness = -1
            if brightness >= max_brightness:
                max_offset = o
                max_brightness = brightness

        joe = (joe[0] + max_offset[0], joe[1] + max_offset[1])
        eaten.append(max_brightness)
        img.putpixel(joe, (0, 0, 0))

    eaten_brightness = float(sum(eaten)) / len(eaten)
    print('%d of %d (score %f)' % (eaten_brightness, total_brightness, eaten_brightness / total_brightness))
    img.show()

test_img('img0.jpg')
test_img('img1.png')
test_img('img2.jpg')
test_img('img3.jpg')
test_img('img4.jpg')

Выход:

llama@llama:~/Code/python/ppcg40069hungrysnake$ ./hungrysnake.py 
15 of 260 (score 0.060699)
9 of 132 (score 0.074200)
16 of 300 (score 0.055557)
4 of 369 (score 0.010836)
79 of 400 (score 0.197266)

Ява (оценка: 0,6949)

Простой алгоритм, который съедает самый яркий пиксель из четырех пикселей, окружающих текущий пиксель. В случае ничьей съедаемый пиксель является случайным, что приводит к различным оценкам и получению изображений при каждом выполнении. Таким образом, приведенные ниже оценки представляют собой средние значения более 50 исполнений на каждом изображении.

Чтобы запустить его, либо отредактируйте три аргумента (существующих как константы класса) в источнике, либо передайте их через командную строку в форме, в java HungryImageSnake <source> <iterations> <printScores>которой <source>находится исходный файл изображения, которое нужно съесть, <iterations>и сколько раз оно съело изображение (принимая средний балл и сохранение лучшего балла за все итерации), и <printScores>это правда, чтобы напечатать балл каждой итерации или ложь, чтобы нет.

import javax.imageio.ImageIO;
import java.awt.Graphics;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;

public class HungryImageSnake {

    private static final String SOURCE = "tornado.jpg";
    private static final int ITERATIONS = 50;
    private static final boolean PRINT_SCORES = true;

    public static void main(String[] args) {
        try {
            String source = args.length > 0 ? args[0] : SOURCE;
            int iterations = args.length > 1 ? Integer.parseInt(args[1]) : ITERATIONS;
            boolean printScores = args.length > 2 ? Boolean.parseBoolean(args[2]) : PRINT_SCORES;

            System.out.printf("Reading '%s'...%n", source);
            System.out.printf("Performing %d meals...%n", iterations);
            BufferedImage image = ImageIO.read(new File(source));
            double totalScore = 0;
            double bestScore = 0;
            BufferedImage bestImage = null;
            for (int i = 0; i < iterations; i++) {
                HungryImageSnake snake = new HungryImageSnake(image);
                while (snake.isHungry()) {
                    snake.eat();
                }
                double score = snake.getScore();
                if (printScores) {
                    System.out.printf("    %d: score of %.4f%n", i + 1, score);
                }
                totalScore += score;
                if (bestImage == null || score > bestScore) {
                    bestScore = score;
                    bestImage = snake.getImage();
                }
            }
            System.out.printf("Average score: %.4f%n", totalScore / iterations);
            String formattedScore = String.format("%.4f", bestScore);
            String output = source.replaceFirst("^(.*?)(\\.[^.]+)?$", "$1-b" + formattedScore + "$2");
            ImageIO.write(bestImage, source.substring(source.lastIndexOf('.') + 1), new File(output));
            System.out.printf("Wrote best image (score: %s) to '%s'.%n", bestScore, output);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private int x;
    private int y;
    private int movesLeft;
    private int maximumMoves;
    private double eatenAverageBrightness;
    private double originalAverageBrightness;
    private BufferedImage image;

    public HungryImageSnake(BufferedImage image) {
        this.image = copyImage(image);
        int size = image.getWidth() * image.getHeight();
        this.maximumMoves = size / 3;
        this.movesLeft = this.maximumMoves;
        int totalBrightness = 0;
        for (int x = 0; x < image.getWidth(); x++) {
            for (int y = 0; y < image.getHeight(); y++) {
                totalBrightness += getBrightnessAt(x, y);
            }
        }
        this.originalAverageBrightness = totalBrightness / (double) size;
    }

    public BufferedImage getImage() {
        return image;
    }

    public double getEatenAverageBrightness() {
        return eatenAverageBrightness;
    }

    public double getOriginalAverageBrightness() {
        return originalAverageBrightness;
    }

    public double getScore() {
        return eatenAverageBrightness / originalAverageBrightness;
    }

    public boolean isHungry() {
        return movesLeft > 0;
    }

    public void eat() {
        if (!isHungry()) {
            return;
        }
        int[][] options = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        shuffleArray(options); // prevent snake from getting stuck in corners
        int[] bestOption = null;
        int bestBrightness = 0;
        for (int[] option : options) {
            int optionX = this.x + option[0];
            int optionY = this.y + option[1];
            if (exists(optionX, optionY)) {
                int brightness = getBrightnessAt(optionX, optionY);
                if (bestOption == null || brightness > bestBrightness) {
                    bestOption = new int[]{ optionX, optionY };
                    bestBrightness = brightness;
                }
            }
        }

        image.setRGB(bestOption[0], bestOption[1], 0);
        this.movesLeft--;
        this.x = bestOption[0];
        this.y = bestOption[1];
        this.eatenAverageBrightness += bestBrightness / (double) maximumMoves;
    }

    private boolean exists(int x, int y) {
        return x >= 0 && x < image.getWidth() && y >= 0 && y < image.getHeight();
    }

    private int getBrightnessAt(int x, int y) {
        int rgb = image.getRGB(x, y);
        int r = (rgb >> 16) & 0xFF;
        int g = (rgb >> 8) & 0xFF;
        int b = rgb & 0xFF;
        return r + g + b;
    }

    private static <T> void shuffleArray(T[] array) {
        Random random = new Random();
        for (int i = array.length - 1; i > 0; i--) {
            int index = random.nextInt(i + 1);
            T temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }

    private static BufferedImage copyImage(BufferedImage source){
        BufferedImage b = new BufferedImage(source.getWidth(), source.getHeight(), source.getType());
        Graphics g = b.getGraphics();
        g.drawImage(source, 0, 0, null);
        g.dispose();
        return b;
    }
}

Средние оценки, по изображению, более пятидесяти итераций:

Bridge - 0.7739
Spheres - 0.5580
Scream - 0.8197
Fractal - 0.3850
Vortex - 0.9158
Tornado - 0.7172

Лучшие результаты по изображениям за те же пятьдесят итераций:

Bridge - 0.8996
Spheres - 0.8741
Scream - 0.9183
Fractal - 0.5720
Vortex - 1.1520
Tornado - 0.9281

Изображения с наибольшим количеством баллов:

Как видно из изображений, фактически съедено гораздо меньше трети пикселей, поскольку змея иногда застревает среди уже съеденных пикселей, на которых она остается в мертвой зоне до тех пор, пока случайность ее движений не приведет ее к съедобная часть изображения.

Кроме того, в результате повторного поедания пикселями змей оценки смещаются вниз, поскольку нулевая яркость битых пикселей снова учитывается в среднем. Я ожидал бы увидеть гораздо более высокие оценки, если бы алгоритм оценки был изменен, чтобы делить его только на количество ходов, которые привели к поеданию новых пикселей, а не всех ходов (включая те, где змея съедает уже мертвый пиксель, который она съела раньше ).

Конечно, лучшим подходом было бы создать эвристику яркости для каждого пикселя и найти путь width * height / 3пикселей с самой высокой средней яркостью, но я сомневаюсь, что этот подход будет оптимальным во время выполнения, особенно на больших изображениях, как число возможных перестановок будет очень большим. Позже я могу попытаться рассмотреть эту форму и опубликовать ее в отдельном ответе, если это так.

Python 2, оценка: 1.205

Некоторое время назад я собрал быстрое решение Python, но забыл опубликовать его. Вот. Он находит самые богатые блоки на изображении, затем перемещается к каждому блоку, съедая все лучшие блоки, которые он получает.

Полученные результаты

bridge.jpg: 591.97866/515.41501 =                               1.14855 
BallsRender.png: 493.24711/387.80635 =                          1.27189 
Mandel_zoom_04_seehorse_tail.jpg: 792.23990/624.60579 =         1.26838 
Red_Vortex_Apophysis_Fractal_Flame.jpg: 368.26121/323.08463 =   1.13983 
The_Scream.jpg: 687.18565/555.05221 =                           1.23806
swirl.jpg: 762.89469/655.73767 =                                1.16341

AVERAGE                                                         1.205

Пример изображения

Код Python 2.7

from pygame.locals import *
import pygame, sys, random

fn = sys.argv[1]

screen = pygame.display.set_mode((1900,1000))
pic = pygame.image.load(fn)
pic.convert()
W,H = pic.get_size()
enough = W*H/3
screen.blit(pic, (0,0))

ORTH = [(-1,0), (1,0), (0,-1), (0,1)]
def orth(p):
    return [(p[0]+dx, p[1]+dy) for dx,dy in ORTH]

def look(p):
    x,y = p
    if 0 <= x < W and 0 <= y < H:
        return sum(pic.get_at(p))
    else:
        return -1

# index picture
locs = [(x,y) for x in range(W) for y in range(H)]
grid = dict( (p,sum(pic.get_at(p))) for p in locs )
rank = sorted( grid.values() )
median = rank[ len(rank)/2 ]
dark = dict( (k,v) for k,v in grid if v < median )
good = dict( (k,v) for k,v in grid if v > median )
pictotal = sum(rank)
picavg = 1.0 * pictotal/(W*H)
print('Indexed')

# compute zone values:
block = 16
xblocks, yblocks = (W-1)/block, (H-1)/block
zones = dict( ((zx,zy),0) for zx in range(xblocks) for zy in range(yblocks) )
for x,y in locs:
    div = (x/block, y/block)
    if div in zones:
        colsum = sum( pic.get_at((x,y)) )
        zones[div] += colsum

# choose best zones:
zonelist = sorted( (v,k) for k,v in zones.items() )
cut = int(xblocks * yblocks * 0.33)
bestzones = dict( (k,v) for v,k in zonelist[-cut:] )

# make segment paths:
segdrop = [(0,1)] * (block-1)
segpass = [(1,0)] * block
segloop = [(0,-1)] * (block-1) + [(1,0)] + [(0,1)] * (block-1)
segeat = ( segloop+[(1,0)] ) * (block/2)
segshort = [(1,0)] * 2 + ( segloop+[(1,0)] ) * (block/2 - 1)

def segtopath(path, seg, xdir):
    for dx,dy in seg:
        x,y = path[-1]
        newloc = (x+dx*xdir, y+dy)
        path.append(newloc)

# design good path:
xdir = 1
path = [(0,0)]
segtopath(path, segdrop, xdir)
shortzone = True
while True:
    x,y = path[-1]
    zone = (x/block, y/block)
    if zone in bestzones:
        if shortzone:
            seg = segshort
        else:
            seg = segeat
    else:
        seg = segpass
    segtopath(path, seg, xdir)
    shortzone = False
    # check end of x block run:
    x,y = path[-1]
    zone = (x/block, y/block)
    if not ( 0 <= x < xblocks*block ):
        del path[-1]
        segtopath(path, segdrop, xdir)
        shortzone = True
        xdir = xdir * -1
    if len(path) > enough:
        break
print('Path Found')

# show path on picture:
loc = path.pop(0)
eaten = 1
joetotal = grid[loc]
i = 0
while eaten <= enough:
    loc = path[i]
    i += 1
    pic.set_at(loc, (0,0,0))
    joetotal += grid[loc]
    eaten += 1
    if i % 1000 == 0:
        screen.blit(pic, (0,0))
        pygame.display.flip()
        for event in pygame.event.get():
            if event.type == QUIT: sys.exit(0)

# save picture and wait:
screen.blit(pic, (0,0))
pygame.display.flip()
pygame.image.save(pic, 'output/'+fn)
joeavg = 1.0 * joetotal/eaten
print '%s: %7.5f/%7.5f = %7.5f' % (fn, joeavg, picavg, joeavg/picavg)
while True:
    for event in pygame.event.get():
        if event.type == QUIT: sys.exit(0)