Allez le rendre étoilé

14

Dans ce concours, vous devez écrire un programme qui accepte une image en pixels noir et blanc et essaie de la modifier, de sorte que la forme blanche forme le domaine étoile , avec le moins de changements possible.

Les modifications autorisées sont de transformer les pixels blancs en noirs et de transformer les pixels noirs en blancs.

La sortie doit à nouveau être constituée de la même image mais cette fois avec tous les changements et avec un / le centre marqué. Les pixels qui sont passés du blanc au noir doivent être affichés en bleu, ceux qui sont passés du noir au blanc doivent être affichés en jaune et au moins un pixel central doit être affiché en rouge. (Les couleurs exactes dépendent de vous.) Le programme doit sortir l'image spécifiée ainsi que le nombre total de modifications qui ont été apportées.

Définitions

Domaine étoile

L'ensemble des pixels blancs de l'image représente un domaine d'étoile si (et seulement si) il y a (au moins) un pixel central . Le pixel central est l'un des pixels blancs qui peuvent être connectés par une ligne droite à tous les autres pixels blancs de sorte que la ligne ne traverse que des pixels blancs. (Le pixel central n'est donc pas nécessairement unique.)

Ligne droite entre deux pixels

Étant donné deux pixels (début et fin, tous deux rouges dans l'illustration ci-dessous), la ligne droite entre les deux pixels se compose de tous les pixels qui touchent la ligne (mathématique, jaune dans l'illustration ci-dessous) qui part du centre du premier pixel au centre du dernier pixel. Un pixel ne touche pas la ligne s'il ne la touche que par un coin, donc pour qu'un pixel appartienne à la ligne de pixel, la ligne (mathématique, jaune) doit traverser le pixel en question avec une longueur non nulle. (S'il ne touche que le point d'angle, cela est considéré comme une longueur nulle). Considérez les exemples suivants:

pixels

Exemple

La première image doit représenter un exemple d'entrée de testcase et les deux autres images représentent deux sorties possibles valides pour l'exemple donné:

exemple de testcase premier exemple de solution deuxième exemple de solution

Les zones jaunes (anciennement noires) comptent également dans le domaine `` blanc '', tandis que les zones bleues (anciennement blanches) comptent dans la partie `` noire '' à l'extérieur du domaine, et le point rouge à chaque fois représente un pixel central possible.

Cas de test

Les cas de test suivants sont des png avec chacun une taille de 256 x 256 pixels.

cas de test 1 cas de test 2 cas de test 3 cas de test 4 cas de test 5 cas de test 6

Notation

Veuillez exécuter votre programme avec les cas de test suivants et inclure la sortie (image / nombre de modifications) dans votre réponse. Je ferai un classement pour chaque cas de test. Votre score sera la somme de chaque classement dans le classement - plus le score est bas, mieux c'est. Des échappatoires standard s'appliquent. Il n'est pas autorisé de faire reconnaître au programme ces cas de test et d'exécuter un cas spécial pour eux. (Il n'est pas autorisé de précalculer et d'enregistrer les pixels centraux optimaux pour chacun de ces cas de test.) Le programme devrait fonctionner pour toutes les images.

Classement

Name        | Score | 1     - rk | 2     - rk | 3     - rk | 4     - rk | 5     - rk | 5     - rk | Total Changes
------------+-------+------------+------------+------------+------------+------------+------------+--------------
Maltysen    |    11 | 28688 -  2 | 24208 -  2 | 24248 -  1 |  7103 -  2 | 11097 -  2 | 13019 -  2 | 108363
TheBestOne  |     7 | 0     -  1 | 13698 -  1 | 24269 -  2 |   103 -  1 |  5344 -  1 |  4456 -  1 |  47867  
flawr
la source
2
Il serait utile d'expliquer la figure 1. Pourquoi connectez-vous des pixels rouges, par exemple?
DavidC
4
Je ne sais pas vraiment ce que tu veux dire. Pouvez-vous donner un avant et un après l'un de vos cas de test?
À quelle distance une ligne doit-elle être proche d'un coin de pixel pour être considérée comme passant?
TheNumberOne
J'ai ajouté quelques exemples et essayé de clarifier le texte, j'espère qu'il est clair maintenant!
flawr
Y a-t-il quelqu'un d'autre qui a l'intention de tenter ce défi? Je suis quelque peu confus, car un grand nombre de personnes ont voté pour ce défi, mais nous n'avons pour l'instant qu'une seule réponse (pas très sérieuse). Des critiques?
2015

Réponses:

4

Java 8, 47 867 changements au total.

Utilise la moyenne de l'image comme point central. Il attire ensuite tous les rayons possibles vers le centre et lui donne le meilleur rayon de couleur. Il colore ensuite tous les points invalides en noir.

import javax.imageio.ImageIO;
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.List;

public class MakeItStarry {

    private static final int RGB_RED = Color.RED.getRGB();
    static int[][] originalImage;

    static final int WHITE = 0;
    static final int BLACK = 1;
    static final int RGB_WHITE = Color.WHITE.getRGB();
    static final int RGB_BLACK = Color.BLACK.getRGB();
    static final int RGB_BLUE = Color.BLUE.getRGB();
    static final int RGB_YELLOW = Color.YELLOW.getRGB();

    public static void main(String[] args) throws Exception{
        originalImage = convert(ImageIO.read(new File(args[0])));
        Point center = findCenter(originalImage);
        int[][] nextImage = starry(originalImage, center);
        BufferedImage result = difference(originalImage, nextImage);
        result.setRGB(center.x, center.y, RGB_RED);
        String fileType;
        String fileName;
        if (args[1].split("\\.").length > 1){
            fileType = args[1].split("\\.")[1];
            fileName = args[1];
        } else {
            fileType = "PNG";
            fileName = args[1] + ".PNG";
        }
        ImageIO.write(result, fileType, new File(fileName));
        System.out.println(cost);
    }

    static int cost;

    private static BufferedImage difference(int[][] image1, int[][] image2) {
        cost = 0;
        int height = image1[0].length;
        int width = image1.length;
        BufferedImage result = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        for (int x = 0; x < width; x++){
            for (int y = 0; y < width; y++){
                if (image1[x][y] == image2[x][y]){
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_WHITE);
                    } else {
                        result.setRGB(x, y, RGB_BLACK);
                    }
                } else {
                    cost++;
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_BLUE);
                    } else {
                        result.setRGB(x, y, RGB_YELLOW);
                    }
                }
            }
        }
        return result;
    }

    private static int[][] starry(int[][] image, Point center) {
        int width = image.length;
        int height = image[0].length;
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                result[x][y] = BLACK;
            }
        }
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++) {
                Point endPoint = new Point(x, y, image);
                List<Point> line = Point.lineTo(center, endPoint, image);
                List<Point> newLine = starRay(line);
                newLine.stream().filter(point -> result[point.x][point.y] == BLACK).forEach(point -> {
                    result[point.x][point.y] = point.color;
                });
            }
        }
        int distance = 0;
        while (distance < height || distance < width){//This removes pixels that can't see the center.
            for (int x = Math.max(center.x - distance,0); x < center.x + distance && x < width; x++){
                for (int y = Math.max(center.y - distance, 0); y < center.y + distance && y < height; y++){
                    Point point = new Point(x, y, result);
                    if (Point.distance(center, point) != distance){
                        continue;
                    }
                    if (point.color == WHITE){
                        List<Point> line = Point.lineTo(center, point, result);
                        for (Point p : line){
                            if (p.color == BLACK){
                                point.color = BLACK;
                                break;
                            }
                        }
                        result[point.x][point.y] = point.color;
                    }
                }
            }//All white pixels can technically see the center but only if looking from the edge.
            distance++;
        }
        return result;
    }

    private static List<Point> starRay(List<Point> line) {
        int numOfWhites = 0;
        int farthestGoodPoint = 0;
        int blackCost = 0;
        int whiteCost = 0;
        for (int i = 0; i < line.size(); i++){
            if (line.get(i).color == WHITE){
                numOfWhites++;
                whiteCost++;
                if (numOfWhites + whiteCost > blackCost){
                    blackCost = 0;
                    whiteCost = 0;
                    farthestGoodPoint = i;
                }
            } else {
                blackCost++;
                numOfWhites = 0;
            }
        }
        List<Point> result = new ArrayList<>();
        for (int i = 0; i < line.size(); i++){
            Point p = line.get(i);
            if (i <= farthestGoodPoint){
                result.add(new Point(p.x, p.y, WHITE));
            } else {
                result.add(new Point(p.x, p.y, BLACK));
            }
        }
        return result;
    }

    private static Point findCenter(int[][] image) {
        double totalx = 0;
        double totaly = 0;
        int counter = 0;
        int width = image.length;
        int height = image[0].length;
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image[x][y] == WHITE){
                    totalx += x;
                    totaly += y;
                    counter++;
                }
            }
        }
        return new Point((int)(totalx/counter), (int)(totaly/counter), image);
    }

    private static int[][] convert(BufferedImage image) {
        int width = image.getWidth();
        int height  = image.getHeight();
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image.getRGB(x, y) == RGB_WHITE){
                    result[x][y] = WHITE;
                } else {
                    result[x][y] = BLACK;
                }
            }
        }
        return result;
    }


    private static class Point {

        public int color;
        public int y;
        public int x;

        public Point(int x, int y, int[][] image) {
            this.x = x;
            this.y = y;
            this.color = image[x][y];
        }

        public Point(int x, int y, int color) {
            this.x = x;
            this.y = y;
            this.color = color;
        }

        public static List<Point> lineTo(Point point1, Point point2, int[][] image) {
            List<Point> result = new ArrayList<>();
            boolean reversed = false;
            if (point1.x > point2.x){
                Point buffer = point1;
                point1 = point2;
                point2 = buffer;
                reversed = !reversed;
            }
            int rise = point1.y - point2.y;
            int run = point1.x - point2.x;
            if (run == 0){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int x = point1.x;
                for (int y = point1.y; y <= point2.y; y++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            if (rise == 0){
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int y = point1.y;
                for (int x = point1.x; x <= point2.x; x++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            int gcd = gcd(rise, run);
            rise /= gcd;
            run /= gcd;
            double slope = (rise + 0.0) / run;
            if (Math.abs(rise) >= Math.abs(run)){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double x = point1.x;
                for (double y = point1.y + .5; y <= point2.y; y++){
                    int px = (int) Math.round(x);
                    if (Math.abs(Math.abs(px - x) - .5) < Math.abs(1.0 / (rise * 4))){
                        x += 1/slope;
                        continue;
                    }
                    result.add(new Point(px, (int) Math.round(y - .5), image));
                    result.add(new Point(px, (int) Math.round(y + .5), image));
                    x += 1/slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            } else {
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double y = point1.y;
                for (double x = point1.x + .5; x <= point2.x; x++){
                    int py = (int) Math.round(y);
                    if (Math.abs(Math.abs(py - y) - .5) < Math.abs(1.0 / (run * 4))) {
                        y += slope;
                        continue;
                    }
                    result.add(new Point((int) Math.round(x - .5), py, image));
                    result.add(new Point((int) Math.round(x + .5), py, image));
                    y += slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
        }

        private static List<Point> reversed(List<Point> points) {
            List<Point> result = new ArrayList<>();
            for (int i = points.size() - 1; i >= 0; i--){
                result.add(points.get(i));
            }
            return result;
        }

        private static int gcd(int num1, int num2) {
            if (num1 < 0 && num2 < 0){
                return -gcd(-num1, -num2);
            }
            if (num1 < 0){
                return gcd(-num1, num2);
            }
            if (num2 < 0){
                return gcd(num1, -num2);
            }
            if (num2 > num1){
                return gcd(num2, num1);
            }
            if (num2 == 0){
                return num1;
            }
            return gcd(num2, num1 % num2);
        }

        @Override
        public String toString(){
            return x + " " + y;
        }

        public static int distance(Point point1, Point point2) {
            return Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y);
        }
    }
}

Résultats

Image 1 - 0 changements, Image 2 - 13 698 changements

12

Image 3 - 24 269 changements, Image 4 - 103 changements

34

Image 5 - 5 344 changements, Image 6 - 4 456 changements

56

Sans pixels non valides supprimés, 42 782 changements au total

Les pixels verts sont la première couche de pixels non valides.

Image 1 - 0 changements, Image 2- 9 889 changements

12

Image 3 - 24 268 changements, Image 4 - 103 changements

34

Image 5 - 4 471 changements, Image 6 - 4 050 changements

56

Tous les pixels blancs dans toutes les images peuvent avoir une ligne tirée vers eux à partir du pixel central si la ligne ne doit pas commencer / se terminer au centre mais plutôt n'importe où sur le pixel.

args[0] contient le nom du fichier d'entrée.

args[1] contient le nom du fichier de sortie.

Imprime en stdoutnombre de modifications.

Le numéro un
la source
Ça a l'air super! Pouvez-vous expliquer ce que vous entendez par «pixels invalides»? Je n'ai pas bien compris ça. Également dans l'image 2 en bas à droite, je ne pouvais pas comprendre pourquoi votre programme `` creuse '' dans le mur noir mais colorie encore les points blancs en noir, mais je pense que cela a à voir avec les `` pixels invalides '', n'est-ce pas?
flawr
Les quelques pixels invalides provoquent un effet de cascade qui en rend beaucoup plus invalides. Je modifierai les dernières images pour afficher la première couche de pixels invalides en vert.
TheNumberOne
3

Python - PIL - 216,228 108,363 changements au total

Whoo! Coupez-le en deux grâce à @AJMansfield! Cet algorithme saute tous les soucis avec le calcul des lignes et l'optimisation et quoi non. Il change juste tous les blancs en noir sauf un. S'il n'y a pas de blancs, cela en fait un noir un blanc. Il vérifie s'il y a plus de blancs ou de noirs et change tous les autres types sauf un. S'il n'y a pas de noir, cela fait (0, 0) le centre.

import Image
from itertools import product

img = Image.open(raw_input())
img = img.convert("RGB")

pixdata = img.load()
changed=0

m=False
count=0
for x, y in product(xrange(img.size[1]), xrange(img.size[0])):
    if pixdata[x, y]==(0, 0, 0):
        count+=1

colors=[(0, 0, 0), (255, 255, 0)] if img.size[0]*img.size[1]-count>count else [(255, 255, 255), (0, 0, 255)]
m=False
for x, y in product(xrange(img.size[1]), xrange(img.size[0])):
    if pixdata[x, y] == colors[0]:
        if m:
            pixdata[x, y] = colors[1]
        else:
            pixdata[x, y] = (255, 0, 0)
            m=True
        changed+=1

if not m:
    pixdata[0, 0]==(255, 0, 0)
    changed+=1
if colors[0]==(255, 255, 255):
    changed-=1

print changed
img.save("out.png", "PNG")

Résultats

Image 1 - 28688 changements, Image 2 - 24208 changements

Image 3 - 24248 changements, Image 4 - 7103 changements

Modifications de l'image 5 - 11097, modifications de l'image 6 - 13019

Prend le nom de fichier de raw_input et écrit dans out.png et imprime le nombre de modifications.

Maltysen
la source
Notez que les pixels qui sont passés du noir au blanc doivent être jaunes dans votre sortie. Ceux qui sont passés du blanc au noir doivent être bleus et le centre (dans votre cas, votre seul pixel "blanc" doit être rouge dans votre sortie. Sinon, merci d'avoir participé =) PS: Il devrait toujours être possible de créer un domaine en étoile, même si vous avez une image entièrement noire en entrée, vous pouvez changer un pixel en blanc (rouge).
flawr
Cela peut être impossible s'il n'y a pas de pixels blancs ou noirs (c'est-à-dire en couleur). En tout cas, je fais les autres changements.
Maltysen
Oh. Image en noir et blanc. Ma faute.
Maltysen
Je pense qu'il pourrait être plus efficace de faire la stratégie inverse et de changer tous les pixels noirs en blancs. Avez-vous essayé cela?
AJMansfield
@AJMansfield Je pense que cela ne serait que plus efficace pour le cas de test donné, donc cela pourrait déjà être considéré comme conditionnant l'algorithme pour les cas de test donnés.
flawr