Иди и сделай это звездным

14

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

Допустимые изменения превращают белые пиксели в черные и превращают черные пиксели в белые.

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

Определения

Звездный Домен

Набор белых пикселей изображения представляет звездный домен, если (и только если) есть (по крайней мере) один центральный пиксель . Центральный пиксель - это один из белых пикселей, который можно соединить прямой линией со всеми остальными белыми пикселями, чтобы эта линия проходила только через белые пиксели. (Центральный пиксель поэтому не обязательно уникален.)

Прямая линия между двумя пикселями

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

пикселей

пример

Первое изображение должно представлять пример тестового набора 'input', а два других изображения представляют два допустимых возможных выхода для данного примера:

пример теста первый пример решения Второй пример решения

Желтые области (ранее черные) также учитываются в «белой» области, в то время как синие области (ранее белые) учитываются в «черной» части вне домена, и красная точка каждый раз представляет один возможный центральный пиксель.

Тестовые случаи

Следующие тесты представляют собой png с размером 256 x 256 пикселей.

контрольный пример 1 контрольный пример 2 контрольный пример 3 контрольный пример 4 контрольный пример 5 контрольный пример 6

счет

Пожалуйста, запустите вашу программу со следующими тестовыми примерами и включите вывод (изображение / количество изменений) в ваш ответ. Я сделаю таблицу лидеров для каждого теста. Ваша оценка будет суммой каждого рейтинга в таблице лидеров - чем ниже оценка, тем лучше. Применяются стандартные лазейки. Запрещается заставлять программу распознавать эти тестовые случаи и запускать для них специальный случай. (Не разрешается предварительно вычислять и сохранять оптимальные центральные пиксели для каждого из этих тестовых случаев.) Программа должна работать для любых изображений.

Leaderboard

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
code-challenge graphical-output optimization image-processing flawr
источник
2
Было бы полезно, если бы вы объяснили рис. 1. Почему вы подключаете, например, красные пиксели?
DavidC
4
Я не совсем уверен, что вы имеете в виду. Можете ли вы дать до и после одного из ваших тестов?
Насколько близко линия должна быть к углу пикселя, чтобы считаться, что она проходит?
TheNumberOne
Я добавил несколько примеров и попытался уточнить текст, надеюсь, теперь это понятно!
flawr
Есть ли кто-нибудь еще, кто собирается попробовать эту задачу? Я несколько сбит с толку, так как довольно много людей проголосовали за этот вызов, но у нас пока есть только один (не очень серьезный) ответ. Есть критика?
15:00

Ответы:

4

Java 8, всего 47 867 изменений.

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

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);
        }
    }
}

Результаты

Изображение 1 - 0 изменений, Изображение 2 - 13 698 изменений

12

Изображение 3 - 24 269 изменений, Изображение 4 - 103 изменений

34

Изображение 5 - 5 344 изменения, Изображение 6 - 4 456 изменений

56

Без удаления недопустимых пикселей, всего 42,782 изменений

Зеленые пиксели - это первый слой недопустимых пикселей.

Изображение 1 - 0 изменений, Изображение 2 - 9,889 изменений

12

Изображение 3 - 24 268 изменений, Изображение 4 - 103 изменений

34

Изображение 5 - 4 471 изменений, Изображение 6 - 4 050 изменений

56

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

args[0] содержит имя входного файла.

args[1] содержит имя выходного файла.

Печать на stdoutколичество изменений.

Номер один
источник
Выглядит отлично! Можете ли вы объяснить, что вы подразумеваете под «недопустимыми пикселями»? Я не совсем понял это. Также на рисунке 2 в правом нижнем углу я не мог понять, почему ваша программа «копает» черную стену, но затем снова окрашивает белые точки в черный, но я думаю, что это связано с «недействительными пикселями», верно?
flawr
Несколько недопустимых пикселей вызывают каскадный эффект, который делает многие другие недействительными. Я изменю последние несколько изображений, чтобы показать первый слой недопустимых пикселей зеленым цветом.
TheNumberOne
3

Python - PIL - всего 216 228 108 363 изменений

Ого! Сократите его пополам благодаря @AJMansfield! Этот алгоритм пропускает все заботы о вычислениях строк и оптимизации, а что нет. Он просто меняет все белые на черный, кроме одного. Если белых нет, то черный становится белым. Он проверяет, есть ли больше белых или черных, и заменяет на него все остальные, кроме одного. Если черных нет, это делает (0, 0) центром.

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")

Результаты

Изображение 1 - 28688 изменений, Изображение 2 - 24208 изменений

Изображение 3 - 24248 изменений, Изображение 4 - 7103 изменений

Изображение 5 - 11097 изменений, Изображение 6 - 13019 изменений

Берет имя файла из raw_input и записывает в out.png и печатает количество изменений.

Maltysen
источник
Обратите внимание, что пиксели, которые были изменены с черного на белый, должны быть желтыми на вашем выходе. То, что было изменено с белого на черный, должно быть синим, а центр (в вашем случае ваш единственный «белый» пиксель должен быть красным в вашем выводе. Кроме этого, спасибо за участие =) PS: Всегда должно быть возможно сделать звездный домен, даже если у вас есть полностью черное изображение на входе, вы можете изменить один пиксель на белый (красный).
flawr
Это может быть невозможно, если нет белых или черных пикселей (то есть полноцветных). В любом случае я делаю другие изменения.
Maltysen
Ой. Черно-белое изображение. Виноват.
Maltysen
Я думаю, что было бы более эффективно использовать противоположную стратегию и заменить все черные пиксели на белые. Вы пробовали это?
AJMansfield
@ AJMansfield Я думаю, что это было бы только более эффективно для данного тестового примера, так что, возможно, это уже можно было бы рассматривать как условие алгоритма для данных тестовых случаев.
flawr