자바 (점수 : 0.6949)

현재 픽셀을 둘러싸고있는 4 개의 픽셀 중 가장 밝은 픽셀을 먹는 간단한 알고리즘입니다. 동점의 경우, 먹은 픽셀은 임의적이며, 점수가 다르고 매 실행마다 이미지가 달라집니다. 따라서 아래 점수는 각 이미지에서 평균 50 회 이상 실행 된 것입니다.

그것을 세 가지 인수는 소스 (클래스 상수로 기존) 중 편집을 실행하거나 형태로 명령 줄을 통해이를 전달하려면 먹을 이미지의 소스 파일, 이미지를 먹는 횟수 (복용입니다 평균 점수 및 모든 반복에서 최고 점수 저장) 및 각 반복의 점수를 인쇄하려면 true 이고, 그렇지 않으면 false입니다.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;
    }
}

이미지를 기준으로 50 회 이상의 평균 점수 :

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

동일한 50 회 반복에서 이미지 별 최고 점수 :

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

가장 높은 점수를받은 런의 이미지 :

이미지에서 알 수 있듯이, 뱀은 이미 먹은 픽셀 사이에 때때로 붙어 있기 때문에 픽셀의 3 분의 1보다 훨씬 적게 실제로 먹습니다.이 지점에서 움직임의 임의성이 나타날 때까지 죽은 영역 내에 붙어 있습니다. 이미지의 식용 부분.

뱀이 다시 먹는 픽셀의 결과로, 데드 픽셀의 제로 밝기가 다시 평균으로 반영되기 때문에 점수가 아래로 바이어스됩니다. 스코어링 알고리즘을 수정하여 모든 움직임이 아닌 새로운 픽셀을 먹는 움직임의 수로 만 나누도록 수정하면 뱀이 이전에 먹은 죽은 픽셀을 먹는 동작을 포함하여 훨씬 더 높은 점수를 기대합니다. ).

물론 더 나은 방법은 각 픽셀에 대해 일종의 밝기 휴리스틱을 생성하고 width * height / 3평균 평균 밝기가 가장 높은 픽셀 의 경로를 찾는 것입니다 . 그러나이 방법은 런타임에서 특히 숫자가 큰 이미지에서 최적 일 것입니다. 가능한 순열의 수가 매우 클 것입니다. 나중에이 접근법의 어떤 형태로 촬영하여 별도의 답변에 게시 할 수 있습니다.

답변

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

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)