Otrzymasz dwa prawdziwe kolorowe obrazy, Źródło i Paletę. Niekoniecznie mają takie same wymiary, ale gwarantuje się, że ich obszary są takie same, tj. Mają taką samą liczbę pikseli.

Twoim zadaniem jest stworzenie algorytmu, który tworzy najdokładniej wyglądającą kopię źródła, używając tylko pikseli w palecie. Każdy piksel w palecie musi zostać użyty dokładnie raz w unikalnej pozycji w tej kopii. Kopia musi mieć takie same wymiary jak Źródło.

Można użyć tego skryptu Python, aby upewnić się, że spełnione są następujące ograniczenia:

from PIL import Image
def check(palette, copy):
    palette = sorted(Image.open(palette).convert('RGB').getdata())
    copy = sorted(Image.open(copy).convert('RGB').getdata())
    print 'Success' if copy == palette else 'Failed'

check('palette.png', 'copy.png')

Oto kilka zdjęć do testowania. Wszystkie mają ten sam obszar. Twój algorytm powinien działać dla dwóch dowolnych obrazów o równych powierzchniach, nie tylko dla gotyku amerykańskiego i Mona Lisy. Powinieneś oczywiście pokazać swoje wyniki.

_{^{Dzięki Wikipedii za zdjęcia słynnych obrazów.}}

Punktacja

To jest konkurs popularności, więc wygrywa najlepiej głosowana odpowiedź. Ale jestem pewien, że istnieje wiele sposobów na kreatywność!

Animacja

millinon wpadł na pomysł, że fajnie byłoby zobaczyć, jak piksele zmieniają się. Też tak myślałem, więc napisałem ten skrypt w języku Python, który pobiera dwa obrazy wykonane w tych samych kolorach i rysuje między nimi obrazy pośrednie. Aktualizacja: Właśnie go poprawiłem, aby każdy piksel przesunął minimalną kwotę, którą musi. To już nie jest losowe.

Po pierwsze, Mona Lisa zamienia się w amerykański gotyk aditsu. Dalej jest amerykański gotyk Bitpwnera (od Mona Lisa), zmieniający się w aditsu. To niesamowite, że obie wersje mają dokładnie taką samą paletę kolorów.

Wyniki są naprawdę zdumiewające. Oto tęcza aditsu Mona Lisa (spowolniona, aby pokazać szczegóły).

Ta ostatnia animacja niekoniecznie jest związana z konkursem. Pokazuje, co się dzieje, gdy mój skrypt jest używany do obracania obrazu o 90 stopni.

Java - GUI z progresywną losową transformacją

Próbowałem wiele rzeczy, niektóre bardzo skomplikowane, a potem wróciłem do tego stosunkowo prostego kodu:

import java.awt.BorderLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;

import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.Timer;

@SuppressWarnings("serial")
public class CopyColors extends JFrame {
    private static final String SOURCE = "spheres";
    private static final String PALETTE = "mona";
    private static final int COUNT = 10000;
    private static final int DELAY = 20;
    private static final int LUM_WEIGHT = 10;

    private static final double[] F = {0.114, 0.587, 0.299};
    private final BufferedImage source;
    protected final BufferedImage dest;
    private final int sw;
    private final int sh;
    private final int n;
    private final Random r = new Random();
    private final JLabel l;

    public CopyColors(final String sourceName, final String paletteName) throws IOException {
        super("CopyColors by aditsu");
        source = ImageIO.read(new File(sourceName + ".png"));
        final BufferedImage palette = ImageIO.read(new File(paletteName + ".png"));
        sw = source.getWidth();
        sh = source.getHeight();
        final int pw = palette.getWidth();
        final int ph = palette.getHeight();
        n = sw * sh;
        if (n != pw * ph) {
            throw new RuntimeException();
        }
        dest = new BufferedImage(sw, sh, BufferedImage.TYPE_INT_RGB);
        for (int i = 0; i < sh; ++i) {
            for (int j = 0; j < sw; ++j) {
                final int x = i * sw + j;
                dest.setRGB(j, i, palette.getRGB(x % pw, x / pw));
            }
        }
        l = new JLabel(new ImageIcon(dest));
        add(l);
        final JButton b = new JButton("Save");
        add(b, BorderLayout.SOUTH);
        b.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(final ActionEvent e) {
                try {
                    ImageIO.write(dest, "png", new File(sourceName + "-" + paletteName + ".png"));
                } catch (IOException ex) {
                    ex.printStackTrace();
                }
            }
        });
    }

    protected double dist(final int x, final int y) {
        double t = 0;
        double lx = 0;
        double ly = 0;
        for (int i = 0; i < 3; ++i) {
            final double xi = ((x >> (i * 8)) & 255) * F[i];
            final double yi = ((y >> (i * 8)) & 255) * F[i];
            final double d = xi - yi;
            t += d * d;
            lx += xi;
            ly += yi;
        }
        double l = lx - ly;
        return t + l * l * LUM_WEIGHT;
    }

    public void improve() {
        final int x = r.nextInt(n);
        final int y = r.nextInt(n);
        final int sx = source.getRGB(x % sw, x / sw);
        final int sy = source.getRGB(y % sw, y / sw);
        final int dx = dest.getRGB(x % sw, x / sw);
        final int dy = dest.getRGB(y % sw, y / sw);
        if (dist(sx, dx) + dist(sy, dy) > dist(sx, dy) + dist(sy, dx)) {
            dest.setRGB(x % sw, x / sw, dy);
            dest.setRGB(y % sw, y / sw, dx);
        }
    }

    public void update() {
        l.repaint();
    }

    public static void main(final String... args) throws IOException {
        final CopyColors x = new CopyColors(SOURCE, PALETTE);
        x.setSize(800, 600);
        x.setLocationRelativeTo(null);
        x.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        x.setVisible(true);
        new Timer(DELAY, new ActionListener() {
            @Override
            public void actionPerformed(final ActionEvent e) {
                for (int i = 0; i < COUNT; ++i) {
                    x.improve();
                }
                x.update();
            }
        }).start();
    }
}

Wszystkie istotne parametry są zdefiniowane jako stałe na początku klasy.

Program najpierw kopiuje obraz palety do wymiarów źródłowych, a następnie wielokrotnie wybiera 2 losowe piksele i zamienia je, jeśli to zbliży je do obrazu źródłowego. „Bliżej” definiuje się za pomocą funkcji odległości koloru, która oblicza różnicę między składnikami r, g, b (ważonymi luma) wraz z całkowitą różnicą luma, przy czym większa waga ma luma.

Formowanie kształtów zajmuje tylko kilka sekund, ale kolory łączą się nieco dłużej. Możesz zapisać bieżący obraz w dowolnym momencie. Zwykle czekałem około 1-3 minut przed zapisaniem.

Wyniki:

W przeciwieństwie do niektórych innych odpowiedzi, wszystkie te obrazy zostały wygenerowane przy użyciu dokładnie tych samych parametrów (innych niż nazwy plików).

Paleta gotycka w stylu amerykańskim

Paleta Mona Lisa

Paleta Gwiaździsta noc

Paleta Krzyk

Paleta kulek

Myślę, że to najtrudniejszy test i każdy powinien opublikować swoje wyniki za pomocą tej palety:

Niestety nie uważam obrazu rzeki za bardzo interesujący, więc go nie uwzględniłem.

Dodałem również film na https://www.youtube.com/watch?v=_-w3cKL5teM , pokazuje on, co robi program (nie dokładnie w czasie rzeczywistym, ale podobny), a następnie pokazuje stopniowy ruch pikseli za pomocą pytona Calvina scenariusz. Niestety jakość wideo jest znacznie uszkodzona przez kodowanie / kompresję youtube.

Jawa

import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import javax.imageio.ImageIO;

/**
 *
 * @author Quincunx
 */
public class PixelRearranger {

    public static void main(String[] args) throws IOException {
        BufferedImage source = ImageIO.read(resource("American Gothic.png"));
        BufferedImage palette = ImageIO.read(resource("Mona Lisa.png"));
        BufferedImage result = rearrange(source, palette);
        ImageIO.write(result, "png", resource("result.png"));
        validate(palette, result);
    }

    public static class MInteger {
        int val;

        public MInteger(int i) {
            val = i;
        }
    }

    public static BufferedImage rearrange(BufferedImage source, BufferedImage palette) {
        BufferedImage result = new BufferedImage(source.getWidth(),
                source.getHeight(), BufferedImage.TYPE_INT_RGB);

        //This creates a list of points in the Source image.
        //Then, we shuffle it and will draw points in that order.
        List<Point> samples = getPoints(source.getWidth(), source.getHeight());
        System.out.println("gotPoints");

        //Create a list of colors in the palette.
        rgbList = getColors(palette);
        Collections.sort(rgbList, rgb);
        rbgList = new ArrayList<>(rgbList);
        Collections.sort(rbgList, rbg);
        grbList = new ArrayList<>(rgbList);
        Collections.sort(grbList, grb);
        gbrList = new ArrayList<>(rgbList);
        Collections.sort(gbrList, gbr);
        brgList = new ArrayList<>(rgbList);
        Collections.sort(brgList, brg);
        bgrList = new ArrayList<>(rgbList);
        Collections.sort(bgrList, bgr);

        while (!samples.isEmpty()) {
            Point currentPoint = samples.remove(0);
            int sourceAtPoint = source.getRGB(currentPoint.x, currentPoint.y);
            int bestColor = search(new MInteger(sourceAtPoint));
            result.setRGB(currentPoint.x, currentPoint.y, bestColor);
        }
        return result;
    }

    public static List<Point> getPoints(int width, int height) {
        HashSet<Point> points = new HashSet<>(width * height);
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                points.add(new Point(x, y));
            }
        }
        List<Point> newList = new ArrayList<>();
        List<Point> corner1 = new LinkedList<>();
        List<Point> corner2 = new LinkedList<>();
        List<Point> corner3 = new LinkedList<>();
        List<Point> corner4 = new LinkedList<>();

        Point p1 = new Point(width / 3, height / 3);
        Point p2 = new Point(width * 2 / 3, height / 3);
        Point p3 = new Point(width / 3, height * 2 / 3);
        Point p4 = new Point(width * 2 / 3, height * 2 / 3);

        newList.add(p1);
        newList.add(p2);
        newList.add(p3);
        newList.add(p4);
        corner1.add(p1);
        corner2.add(p2);
        corner3.add(p3);
        corner4.add(p4);
        points.remove(p1);
        points.remove(p2);
        points.remove(p3);
        points.remove(p4);

        long seed = System.currentTimeMillis();
        Random c1Random = new Random(seed += 179426549); //The prime number pushes the first numbers apart
        Random c2Random = new Random(seed += 179426549); //Or at least I think it does.
        Random c3Random = new Random(seed += 179426549);
        Random c4Random = new Random(seed += 179426549);

        Dir NW = Dir.NW;
        Dir N = Dir.N;
        Dir NE = Dir.NE;
        Dir W = Dir.W;
        Dir E = Dir.E;
        Dir SW = Dir.SW;
        Dir S = Dir.S;
        Dir SE = Dir.SE;
        while (!points.isEmpty()) {
            putPoints(newList, corner1, c1Random, points, NW, N, NE, W, E, SW, S, SE);
            putPoints(newList, corner2, c2Random, points, NE, N, NW, E, W, SE, S, SW);
            putPoints(newList, corner3, c3Random, points, SW, S, SE, W, E, NW, N, NE);
            putPoints(newList, corner4, c4Random, points, SE, S, SW, E, W, NE, N, NW);
        }
        return newList;
    }

    public static enum Dir {
        NW(-1, -1), N(0, -1), NE(1, -1), W(-1, 0), E(1, 0), SW(-1, 1), S(0, 1), SE(1, 1);
        final int dx, dy;

        private Dir(int dx, int dy) {
            this.dx = dx;
            this.dy = dy;
        }

        public Point add(Point p) {
            return new Point(p.x + dx, p.y + dy);
        }
    }

    public static void putPoints(List<Point> newList, List<Point> listToAddTo, Random rand,
                                 HashSet<Point> points, Dir... adj) {
        List<Point> newPoints = new LinkedList<>();
        for (Iterator<Point> iter = listToAddTo.iterator(); iter.hasNext();) {
            Point p = iter.next();
            Point pul = adj[0].add(p);
            Point pu = adj[1].add(p);
            Point pur = adj[2].add(p);
            Point pl = adj[3].add(p);
            Point pr = adj[4].add(p);
            Point pbl = adj[5].add(p);
            Point pb = adj[6].add(p);
            Point pbr = adj[7].add(p);
            int allChosen = 0;
            if (points.contains(pul)) {
                if (rand.nextInt(5) == 0) {
                    allChosen++;
                    newPoints.add(pul);
                    newList.add(pul);
                    points.remove(pul);
                }
            } else {
                allChosen++;
            }
            if (points.contains(pu)) {
                if (rand.nextInt(5) == 0) {
                    allChosen++;
                    newPoints.add(pu);
                    newList.add(pu);
                    points.remove(pu);
                }
            } else {
                allChosen++;
            }
            if (points.contains(pur)) {
                if (rand.nextInt(3) == 0) {
                    allChosen++;
                    newPoints.add(pur);
                    newList.add(pur);
                    points.remove(pur);
                }
            } else {
                allChosen++;
            }
            if (points.contains(pl)) {
                if (rand.nextInt(5) == 0) {
                    allChosen++;
                    newPoints.add(pl);
                    newList.add(pl);
                    points.remove(pl);
                }
            } else {
                allChosen++;
            }
            if (points.contains(pr)) {
                if (rand.nextInt(2) == 0) {
                    allChosen++;
                    newPoints.add(pr);
                    newList.add(pr);
                    points.remove(pr);
                }
            } else {
                allChosen++;
            }
            if (points.contains(pbl)) {
                if (rand.nextInt(5) == 0) {
                    allChosen++;
                    newPoints.add(pbl);
                    newList.add(pbl);
                    points.remove(pbl);
                }
            } else {
                allChosen++;
            }
            if (points.contains(pb)) {
                if (rand.nextInt(3) == 0) {
                    allChosen++;
                    newPoints.add(pb);
                    newList.add(pb);
                    points.remove(pb);
                }
            } else {
                allChosen++;
            }
            if (points.contains(pbr)) {
                newPoints.add(pbr);
                newList.add(pbr);
                points.remove(pbr);
            }
            if (allChosen == 7) {
                iter.remove();
            }
        }
        listToAddTo.addAll(newPoints);
    }

    public static List<MInteger> getColors(BufferedImage img) {
        int width = img.getWidth();
        int height = img.getHeight();
        List<MInteger> colors = new ArrayList<>(width * height);
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                colors.add(new MInteger(img.getRGB(x, y)));
            }
        }
        return colors;
    }

    public static int search(MInteger color) {
        int rgbIndex = binarySearch(rgbList, color, rgb);
        int rbgIndex = binarySearch(rbgList, color, rbg);
        int grbIndex = binarySearch(grbList, color, grb);
        int gbrIndex = binarySearch(gbrList, color, gbr);
        int brgIndex = binarySearch(brgList, color, brg);
        int bgrIndex = binarySearch(bgrList, color, bgr);

        double distRgb = dist(rgbList.get(rgbIndex), color);
        double distRbg = dist(rbgList.get(rbgIndex), color);
        double distGrb = dist(grbList.get(grbIndex), color);
        double distGbr = dist(gbrList.get(gbrIndex), color);
        double distBrg = dist(brgList.get(brgIndex), color);
        double distBgr = dist(bgrList.get(bgrIndex), color);

        double minDist = Math.min(Math.min(Math.min(Math.min(Math.min(
                distRgb, distRbg), distGrb), distGbr), distBrg), distBgr);

        MInteger ans;
        if (minDist == distRgb) {
            ans = rgbList.get(rgbIndex);
        } else if (minDist == distRbg) {
            ans = rbgList.get(rbgIndex);
        } else if (minDist == distGrb) {
            ans = grbList.get(grbIndex);
        } else if (minDist == distGbr) {
            ans = grbList.get(grbIndex);
        } else if (minDist == distBrg) {
            ans = grbList.get(rgbIndex);
        } else {
            ans = grbList.get(grbIndex);
        }
        rgbList.remove(ans);
        rbgList.remove(ans);
        grbList.remove(ans);
        gbrList.remove(ans);
        brgList.remove(ans);
        bgrList.remove(ans);
        return ans.val;
    }

    public static int binarySearch(List<MInteger> list, MInteger val, Comparator<MInteger> cmp){
        int index = Collections.binarySearch(list, val, cmp);
        if (index < 0) {
            index = ~index;
            if (index >= list.size()) {
                index = list.size() - 1;
            }
        }
        return index;
    }

    public static double dist(MInteger color1, MInteger color2) {
        int c1 = color1.val;
        int r1 = (c1 & 0xFF0000) >> 16;
        int g1 = (c1 & 0x00FF00) >> 8;
        int b1 = (c1 & 0x0000FF);

        int c2 = color2.val;
        int r2 = (c2 & 0xFF0000) >> 16;
        int g2 = (c2 & 0x00FF00) >> 8;
        int b2 = (c2 & 0x0000FF);

        int dr = r1 - r2;
        int dg = g1 - g2;
        int db = b1 - b2;
        return Math.sqrt(dr * dr + dg * dg + db * db);
    }

    //This method is here solely for my ease of use (I put the files under <Project Name>/Resources/ )
    public static File resource(String fileName) {
        return new File(System.getProperty("user.dir") + "/Resources/" + fileName);
    }

    static List<MInteger> rgbList;
    static List<MInteger> rbgList;
    static List<MInteger> grbList;
    static List<MInteger> gbrList;
    static List<MInteger> brgList;
    static List<MInteger> bgrList;
    static Comparator<MInteger> rgb = (color1, color2) -> color1.val - color2.val;
    static Comparator<MInteger> rbg = (color1, color2) -> {
        int c1 = color1.val;
        int c2 = color2.val;
        c1 = ((c1 & 0xFF0000)) | ((c1 & 0x00FF00) >> 8) | ((c1 & 0x0000FF) << 8);
        c2 = ((c2 & 0xFF0000)) | ((c2 & 0x00FF00) >> 8) | ((c2 & 0x0000FF) << 8);
        return c1 - c2;
    };
    static Comparator<MInteger> grb = (color1, color2) -> {
        int c1 = color1.val;
        int c2 = color2.val;
        c1 = ((c1 & 0xFF0000) >> 8) | ((c1 & 0x00FF00) << 8) | ((c1 & 0x0000FF));
        c2 = ((c2 & 0xFF0000) >> 8) | ((c2 & 0x00FF00) << 8) | ((c2 & 0x0000FF));
        return c1 - c2;
    };

    static Comparator<MInteger> gbr = (color1, color2) -> {
        int c1 = color1.val;
        int c2 = color2.val;
        c1 = ((c1 & 0xFF0000) >> 16) | ((c1 & 0x00FF00) << 8) | ((c1 & 0x0000FF) << 8);
        c2 = ((c2 & 0xFF0000) >> 16) | ((c2 & 0x00FF00) << 8) | ((c2 & 0x0000FF) << 8);
        return c1 - c2;
    };

    static Comparator<MInteger> brg = (color1, color2) -> {
        int c1 = color1.val;
        int c2 = color2.val;
        c1 = ((c1 & 0xFF0000) >> 8) | ((c1 & 0x00FF00) >> 8) | ((c1 & 0x0000FF) << 16);
        c2 = ((c2 & 0xFF0000) >> 8) | ((c2 & 0x00FF00) >> 8) | ((c2 & 0x0000FF) << 16);
        return c1 - c2;
    };

    static Comparator<MInteger> bgr = (color1, color2) -> {
        int c1 = color1.val;
        int c2 = color2.val;
        c1 = ((c1 & 0xFF0000) >> 16) | ((c1 & 0x00FF00)) | ((c1 & 0x0000FF) << 16);
        c2 = ((c2 & 0xFF0000) >> 16) | ((c2 & 0x00FF00)) | ((c2 & 0x0000FF) << 16);
        return c1 - c2;
    };

    public static void validate(BufferedImage palette, BufferedImage result) {
        List<Integer> paletteColors = getTrueColors(palette);
        List<Integer> resultColors = getTrueColors(result);
        Collections.sort(paletteColors);
        Collections.sort(resultColors);
        System.out.println(paletteColors.equals(resultColors));
    }

    public static List<Integer> getTrueColors(BufferedImage img) {
        int width = img.getWidth();
        int height = img.getHeight();
        List<Integer> colors = new ArrayList<>(width * height);
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                colors.add(img.getRGB(x, y));
            }
        }
        Collections.sort(colors);
        return colors;
    }
}

Moje podejście polega na znalezieniu najbliższego koloru dla każdego piksela (cóż, prawdopodobnie najbliższego) w 3-przestrzeni, ponieważ kolory są trójwymiarowe.

Działa to poprzez utworzenie listy wszystkich punktów, które musimy wypełnić, oraz listy wszystkich możliwych kolorów, których możemy użyć. Losujemy listę punktów (aby obraz okazał się lepszy), następnie przechodzimy przez każdy punkt i uzyskujemy kolor obrazu źródłowego.

Aktualizacja: Kiedyś po prostu wyszukiwałem binarnie, więc czerwony pasował lepiej niż zielony, który pasował lepiej niż niebieski. Teraz zmieniłem to, aby wykonać sześć wyszukiwań binarnych (wszystkie możliwe permutacje), a następnie wybrać najbliższy kolor. Zajmuje to tylko ~ 6 razy dłużej (tj. 1 minutę). Podczas gdy zdjęcia są nadal ziarniste, kolory pasują lepiej.

Aktualizacja 2: Nie losuję już listy. Zamiast tego wybieram 4 punkty zgodnie z zasadą trzeciej części, a następnie losowo układam punkty, preferując wypełnienie środka.

Uwaga: Zobacz historię zmian starych zdjęć.

Mona Lisa -> Rzeka:

Mona Lisa -> American Gothic:

Mona Lisa -> Kule Raytraced:

Gwiaździsta noc -> Mona Lisa:

Oto animowany gif przedstawiający budowę obrazu:

I pokazując piksele pobrane z Mona Lisa:

Perl, z przestrzenią kolorów Lab i ditheringiem

Uwaga: teraz mam rozwiązanie C. zbyt.

Stosuje podobne podejście do aditsu (wybierz dwie losowe pozycje i zamień piksele w tych pozycjach, jeśli obraz będzie bardziej podobny do obrazu docelowego), z dwiema istotnymi ulepszeniami:

1. Wykorzystuje przestrzeń kolorów CIE L a b * do porównywania kolorów - metryka euklidesowa w tej przestrzeni jest bardzo dobrym przybliżeniem różnicy postrzegania między dwoma kolorami, więc odwzorowanie kolorów powinno być dokładniejsze niż RGB, a nawet HSV / HSL.
2. Po pierwszym przejściu umieszczając piksele w najlepszej możliwej pojedynczej pozycji, wykonuje dodatkowe przejście z losowym ditherem. Zamiast porównywać wartości pikseli w dwóch pozycjach wymiany, oblicza średnią wartość pikseli w sąsiedztwie 3x3 wyśrodkowanym w pozycjach wymiany. Jeśli zamiana poprawia średnie kolory okolic, jest to dozwolone, nawet jeśli powoduje to, że poszczególne piksele są mniej dokładne. W przypadku niektórych par obrazów ma to wątpliwy wpływ na jakość (i sprawia, że ​​efekt palety jest mniej uderzający), ale w przypadku niektórych (takich jak sfery -> cokolwiek) bardzo pomaga. Współczynnik „szczegółów” podkreśla centralny piksel w różnym stopniu. Zwiększenie go zmniejsza ogólną ilość roztrząsania, ale zachowuje więcej szczegółów z obrazu docelowego. Optymalizacja porzucona jest wolniejsza,

Uśrednianie wartości laboratoryjnych, podobnie jak dither, nie jest tak naprawdę uzasadnione (należy je przekonwertować na XYZ, uśrednić i przekonwertować z powrotem), ale do tych celów działa dobrze.

Te obrazy mają limity zakończenia 100 i 200 (zakończ pierwszą fazę, gdy zaakceptowano mniej niż 1 na 5000 zamian, a drugą fazę przy 1 na 2500), a współczynnik szczegółowości ditheringu wynosi 12 (nieco ciaśniejszy roztrząsanie niż w poprzednim zestawie ). Przy tym ustawieniu bardzo wysokiej jakości generowanie obrazów zajmuje dużo czasu, ale przy równoległości cała praca wciąż kończy się w ciągu godziny na moim 6-rdzeniowym urządzeniu. Podbijanie wartości do około 500 kończy zdjęcia w ciągu kilku minut, po prostu wyglądają nieco mniej dopracowane. Chciałem pokazać algorytm najlepiej tutaj.

Kod wcale nie jest ładny:

#!/usr/bin/perl
use strict;
use warnings;
use Image::Magick;
use Graphics::ColorObject 'RGB_to_Lab';
use List::Util qw(sum max);

my $source = Image::Magick->new;
$source->Read($ARGV[0]);
my $target = Image::Magick->new;
$target->Read($ARGV[1]);
my ($limit1, $limit2, $detail) = @ARGV[2,3,4];

my ($width, $height) = ($target->Get('width'), $target->Get('height'));

# Transfer the pixels of the $source onto a new canvas with the diemnsions of $target
$source->Set(magick => 'RGB');
my $img = Image::Magick->new(size => "${width}x${height}", magick => 'RGB', depth => 8);
$img->BlobToImage($source->ImageToBlob);

my ($made, $rejected) = (0,0);

system("rm anim/*.png");

my (@img_lab, @target_lab);
for my $x (0 .. $width) {
  for my $y (0 .. $height) {
    $img_lab[$x][$y] = RGB_to_Lab([$img->getPixel(x => $x, y => $y)], 'sRGB');
    $target_lab[$x][$y] = RGB_to_Lab([$target->getPixel(x => $x, y => $y)], 'sRGB');
  }
}

my $n = 0;
my $frame = 0;
my $mode = 1;

while (1) {
  $n++;

  my $swap = 0;
  my ($x1, $x2, $y1, $y2) = (int rand $width, int rand $width, int rand $height, int rand $height);
  my ($dist, $dist_swapped);

  if ($mode == 1) {
    $dist = (sum map { ($img_lab[$x1][$y1][$_] - $target_lab[$x1][$y1][$_])**2 } 0..2)
          + (sum map { ($img_lab[$x2][$y2][$_] - $target_lab[$x2][$y2][$_])**2 } 0..2);

    $dist_swapped = (sum map { ($img_lab[$x2][$y2][$_] - $target_lab[$x1][$y1][$_])**2 } 0..2)
                  + (sum map { ($img_lab[$x1][$y1][$_] - $target_lab[$x2][$y2][$_])**2 } 0..2);

  } else { # dither mode
    my $xoffmin = ($x1 == 0 || $x2 == 0 ? 0 : -1);
    my $xoffmax = ($x1 == $width - 1 || $x2 == $width - 1 ? 0 : 1);
    my $yoffmin = ($y1 == 0 || $y2 == 0 ? 0 : -1);
    my $yoffmax = ($y1 == $height - 1 || $y2 == $height - 1 ? 0 : 1);

    my (@img1, @img2, @target1, @target2, $points);
    for my $xoff ($xoffmin .. $xoffmax) {
      for my $yoff ($yoffmin .. $yoffmax) {
        $points++;
        for my $chan (0 .. 2) {
          $img1[$chan] += $img_lab[$x1+$xoff][$y1+$yoff][$chan];
          $img2[$chan] += $img_lab[$x2+$xoff][$y2+$yoff][$chan];
          $target1[$chan] += $target_lab[$x1+$xoff][$y1+$yoff][$chan];
          $target2[$chan] += $target_lab[$x2+$xoff][$y2+$yoff][$chan];
        }
      }
    }

    my @img1s = @img1;
    my @img2s = @img2;
    for my $chan (0 .. 2) {
      $img1[$chan] += $img_lab[$x1][$y1][$chan] * ($detail - 1);
      $img2[$chan] += $img_lab[$x2][$y2][$chan] * ($detail - 1);

      $target1[$chan] += $target_lab[$x1][$y1][$chan] * ($detail - 1);
      $target2[$chan] += $target_lab[$x2][$y2][$chan] * ($detail - 1);

      $img1s[$chan] += $img_lab[$x2][$y2][$chan] * $detail - $img_lab[$x1][$y1][$chan];
      $img2s[$chan] += $img_lab[$x1][$y1][$chan] * $detail - $img_lab[$x2][$y2][$chan];
    }

    $dist = (sum map { ($img1[$_] - $target1[$_])**2 } 0..2)
          + (sum map { ($img2[$_] - $target2[$_])**2 } 0..2);

    $dist_swapped = (sum map { ($img1s[$_] - $target1[$_])**2 } 0..2)
                  + (sum map { ($img2s[$_] - $target2[$_])**2 } 0..2);

  }

  if ($dist_swapped < $dist) {
    my @pix1 = $img->GetPixel(x => $x1, y => $y1);
    my @pix2 = $img->GetPixel(x => $x2, y => $y2);
    $img->SetPixel(x => $x1, y => $y1, color => \@pix2);
    $img->SetPixel(x => $x2, y => $y2, color => \@pix1);
    ($img_lab[$x1][$y1], $img_lab[$x2][$y2]) = ($img_lab[$x2][$y2], $img_lab[$x1][$y1]);
    $made ++;
  } else {
    $rejected ++;
  }

  if ($n % 50000 == 0) {
#    print "Made: $made Rejected: $rejected\n";
    $img->Write('png:out.png');
    system("cp", "out.png", sprintf("anim/frame%05d.png", $frame++));
    if ($mode == 1 and $made < $limit1) {
      $mode = 2;
      system("cp", "out.png", "nodither.png");
    } elsif ($mode == 2 and $made < $limit2) {
      last;
    }
    ($made, $rejected) = (0, 0);
  }
}

Wyniki

Paleta gotycka w stylu amerykańskim

Mała różnica tutaj z ditheringiem czy nie.

Paleta Mona Lisa

Dithering zmniejsza pasy na sferach, ale nie jest szczególnie ładny.

Paleta Gwiaździsta noc

Mona Lisa zachowuje nieco więcej szczegółów przy ditheringu. Sfery są mniej więcej w tej samej sytuacji, co ostatnio.

Paleta krzyków

Gwiaździsta noc bez ditheringu to najbardziej niesamowita rzecz na świecie. Dithering sprawia, że ​​jest dokładniejszy pod względem zdjęć, ale o wiele mniej interesujący.

Paleta kulek

Jak mówi aditsu, prawdziwy test. Myślę, że zdaję.

Roztrząsanie bardzo pomaga w przypadku American Gothic i Mona Lisa, łącząc niektóre szarości i inne kolory z bardziej intensywnymi pikselami, aby uzyskać pół-dokładne odcienie skóry zamiast okropnych plam. Krzyk jest mniej dotknięty.

Camaro - Mustang

Źródło obrazów z postu flawr.

Camaro:

Mustang:

Paleta Camaro

Wygląda całkiem dobrze bez wahania.

„Ciasny” dither (taki sam współczynnik szczegółowości jak powyżej) niewiele się zmienia, dodaje tylko trochę szczegółów w podświetleniach maski i dachu.

„Luźny” dither (współczynnik detali spadł do 6) naprawdę wygładza tonację, a przez szybę przednią widać znacznie więcej szczegółów, ale wzory ditheringu są wszędzie bardziej widoczne.

Paleta Mustang

Części samochodu wyglądają świetnie, ale szare piksele wyglądają glitchy. Co gorsza, wszystkie ciemniejsze żółte piksele zostały rozmieszczone na czerwonym ciele Camaro, a algorytm nie ditherujący nie może znaleźć nic wspólnego z jaśniejszymi (przeniesienie ich do samochodu pogorszyłoby dopasowanie, a przeniesienie ich do innego punkt na tle nie ma znaczenia), więc w tle jest duch-Mustang.

Roztrząsanie jest w stanie rozłożyć te dodatkowe żółte piksele wokół, aby się nie dotykały, rozrzucając je mniej więcej równomiernie na tle w tym procesie. Rozjaśnienia i cienie w samochodzie wyglądają nieco lepiej.

Ponownie, luźny dither ma najbardziej wyrównaną tonację, odsłania więcej szczegółów na reflektorach i przedniej szybie. Samochód prawie znów wygląda na czerwony. z jakiegoś powodu tło jest zbrylone. Nie jestem pewien, czy mi się podoba.

Wideo

( Link do centrali )

Pyton

Pomysł jest prosty: każdy piksel ma punkt w przestrzeni 3D RGB. Celem jest dopasowanie każdego piksela źródła i jednego obrazu docelowego, najlepiej powinny być „bliskie” (reprezentować „ten sam” kolor). Ponieważ mogą być dystrybuowane na różne sposoby, nie możemy po prostu dopasować najbliższego sąsiada.

Strategia

Niech nbędzie liczbą całkowitą (małą, 3-255 lub więcej). Teraz chmurka pikseli w przestrzeni RGB jest sortowana według pierwszej osi (R). Ten zestaw pikseli jest teraz podzielony na n partycji. Każda z partycji jest teraz sortowana wzdłuż drugiej osi (B), która również jest sortowana w ten sam sposób. Robimy to z obydwoma zdjęciami i mamy teraz dla obu tablicę punktów. Teraz możemy po prostu dopasować piksele według ich pozycji w tablicy, piksel w tej samej pozycji w każdej tablicy ma podobną pozycję w stosunku do każdej chmury pikseli w przestrzeni RGB.

Jeśli rozkład pikseli w przestrzeni RGB obu obrazów jest podobny (oznacza tylko przesunięcie i / lub rozciągnięcie wzdłuż 3 osi), wynik będzie dość przewidywalny. Jeśli rozkłady wyglądają zupełnie inaczej, ten algorytm nie da tak dobrych wyników (jak widać w ostatnim przykładzie), ale myślę, że jest to również jeden z trudniejszych przypadków. Nie wykorzystuje efektów interakcji sąsiednich pikseli w percepcji.

Kod

Oświadczenie: Jestem absolutnym nowicjuszem w Pythonie.

from PIL import Image

n = 5 #number of partitions per channel.

src_index = 3 #index of source image
dst_index = 2 #index of destination image

images =  ["img0.bmp","img1.bmp","img2.bmp","img3.bmp"];
src_handle = Image.open(images[src_index])
dst_handle = Image.open(images[dst_index])
src = src_handle.load()
dst = dst_handle.load()
assert src_handle.size[0]*src_handle.size[1] == dst_handle.size[0]*dst_handle.size[1],"images must be same size"

def makePixelList(img):
    l = []
    for x in range(img.size[0]):
        for y in range(img.size[1]):
            l.append((x,y))
    return l

lsrc = makePixelList(src_handle)
ldst = makePixelList(dst_handle)

def sortAndDivide(coordlist,pixelimage,channel): #core
    global src,dst,n
    retlist = []
    #sort
    coordlist.sort(key=lambda t: pixelimage[t][channel])
    #divide
    partitionLength = int(len(coordlist)/n)
    if partitionLength <= 0:
        partitionLength = 1
    if channel < 2:
        for i in range(0,len(coordlist),partitionLength):
            retlist += sortAndDivide(coordlist[i:i+partitionLength],pixelimage,channel+1)
    else:
        retlist += coordlist
    return retlist

print(src[lsrc[0]])

lsrc = sortAndDivide(lsrc,src,0)
ldst = sortAndDivide(ldst,dst,0)

for i in range(len(ldst)):
    dst[ldst[i]] = src[lsrc[i]]

dst_handle.save("exchange"+str(src_index)+str(dst_index)+".png")

Wynik

Myślę, że nie było źle, biorąc pod uwagę proste rozwiązanie. Możesz oczywiście uzyskać lepsze wyniki, majstrując przy parametrze lub najpierw przekształcając kolory w inną przestrzeń kolorów, a nawet optymalizując partycjonowanie.

Pełna galeria tutaj: https://imgur.com/a/hzaAm#6

Szczegółowe dla rzeki

monalisa> rzeka

ludzie> rzeka

piłki> rzeka

gwiaździsta noc> rzeka

płacz> rzeka

piłki> MonaLisa, zmieniające się n = 2,4,6, ..., 20

To było najtrudniejsze zadanie, myślę, że daleki od ładnych zdjęć, tutaj gif (musiał zostać zredukowany do 256 kolorów) o różnych wartościach parametrów n = 2,4,6, ..., 20. Zaskakujące było dla mnie to, że bardzo niskie wartości dawały lepsze obrazy (patrząc na twarz pani Lisa):

Przepraszam, nie mogę przestać

Który bardziej ci się podoba? Chevy Camaro czy Ford Mustang? Być może tę technikę można ulepszyć i zastosować do kolorowania zdjęć bw. Teraz tutaj: najpierw wyciąłem samochody z grubsza z tła, malując je na biało (w farbie, niezbyt profesjonalnie ...), a następnie użyłem programu python w każdym kierunku.

Są pewne artefakty, myślę, że ponieważ powierzchnia jednego samochodu była nieco większa od drugiej i ponieważ moje umiejętności artystyczne są dość złe =)

Python - Teoretycznie optymalne rozwiązanie

Mówię teoretycznie optymalny, ponieważ naprawdę optymalne rozwiązanie nie jest całkiem możliwe do obliczenia. Zaczynam od opisu rozwiązania teoretycznego, a następnie wyjaśniam, jak poprawiłem go, aby był wykonalny obliczeniowo zarówno w czasie, jak i przestrzeni.

Uważam, że najbardziej optymalnym rozwiązaniem jest to, które daje najniższy całkowity błąd we wszystkich pikselach między starymi i nowymi obrazami. Błąd między dwoma pikselami jest definiowany jako odległość euklidesowa między punktami w przestrzeni 3D, w których każda wartość koloru (R, G, B) jest współrzędną. W praktyce, ze względu na to, jak ludzie postrzegają rzeczy, optymalne rozwiązanie może nie być najlepiej wyglądającym rozwiązaniem. Wydaje się jednak, że we wszystkich przypadkach działa całkiem dobrze.

Aby obliczyć mapowanie, uznałem to za problem dwustronnego dopasowywania masy minimalnej . Innymi słowy, istnieją dwa zestawy węzłów: piksele oryginalne i piksele palety. Krawędź jest tworzona między każdym pikselem w dwóch zestawach (ale żadne krawędzie nie są tworzone w zestawie). Koszt lub waga krawędzi to odległość euklidesowa między dwoma pikselami, jak opisano powyżej. Im bliższe są dwa kolory, tym niższy jest koszt między pikselami.

To tworzy macierz kosztów o rozmiarze N ² . W przypadku tych obrazów, w których N = 123520, wymagane jest około 40 GB pamięci do przedstawienia kosztów jako liczb całkowitych, a połowa z nich jako krótkich liczb całkowitych. Tak czy inaczej, nie miałem wystarczającej ilości pamięci na moim komputerze, aby podjąć próbę. Inną kwestią jest to, że algorytm węgierski lub algorytm Jonkera-Volgenanta , którego można użyć do rozwiązania tego problemu, działał w czasie N ³ . Chociaż zdecydowanie można je obliczyć, wygenerowanie rozwiązania na zdjęcie zajęłoby prawdopodobnie godziny lub dni.

Aby obejść ten problem, losowo sortuję obie listy pikseli, dzielę listy na części C, uruchamiam implementację C ++ algorytmu Jonker-Volgenant na każdej parze list podrzędnych, a następnie łączę listy z powrotem, aby utworzyć ostateczne mapowanie. Dlatego poniższy kod pozwoliłby znaleźć naprawdę optymalne rozwiązanie, pod warunkiem, że ustawimy wielkość porcji C na 1 (bez porcji) i będziemy mieć wystarczającą ilość pamięci. Dla tych zdjęć ustawiam C na 16, tak że N staje się 7720, zajmuje tylko kilka minut na zdjęcie.

Prostym sposobem na zastanowienie się, dlaczego to działa, jest losowe sortowanie listy pikseli, a następnie pobranie podzbioru jest jak próbkowanie obrazu. Zatem ustawienie C = 16 przypomina pobieranie 16 różnych losowych próbek o rozmiarze N / C zarówno z oryginału, jak i palety. To prawda, że ​​istnieją prawdopodobnie lepsze sposoby podziału list, ale podejście losowe zapewnia przyzwoite wyniki.

import subprocess
import multiprocessing as mp
import sys
import os
import sge
from random import shuffle
from PIL import Image
import numpy as np
import LAPJV
import pdb

def getError(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2 + (p1[2]-p2[2])**2

def getCostMatrix(pallete_list, source_list):
    num_pixels = len(pallete_list)
    matrix = np.zeros((num_pixels, num_pixels))

    for i in range(num_pixels):
        for j in range(num_pixels):
            matrix[i][j] = getError(pallete_list[i], source_list[j])

    return matrix

def chunks(l, n):
    if n < 1:
        n = 1
    return [l[i:i + n] for i in range(0, len(l), n)]

def imageToColorList(img_file):
    i = Image.open(img_file)

    pixels = i.load()
    width, height = i.size

    all_pixels = []
    for x in range(width):
        for y in range(height):
            pixel = pixels[x, y]
            all_pixels.append(pixel)

    return all_pixels

def colorListToImage(color_list, old_img_file, new_img_file, mapping):
    i = Image.open(old_img_file)

    pixels = i.load()
    width, height = i.size
    idx = 0

    for x in range(width):
        for y in range(height):
            pixels[x, y] = color_list[mapping[idx]]
            idx += 1

    i.save(new_img_file)

def getMapping(pallete_list, source_list):
    matrix = getCostMatrix(source_list, pallete_list)
    result = LAPJV.lap(matrix)[1]
    ret = []
    for i in range(len(pallete_list)):
        ret.append(result[i])
    return ret

def randomizeList(l):
    rdm_l = list(l)
    shuffle(rdm_l)
    return rdm_l

def getPartialMapping(zipped_chunk):
    pallete_chunk = zipped_chunk[0]
    source_chunk = zipped_chunk[1]
    subl_pallete = map(lambda v: v[1], pallete_chunk)
    subl_source = map(lambda v: v[1], source_chunk)
    mapping = getMapping(subl_pallete, subl_source)
    return mapping

def getMappingWithPartitions(pallete_list, source_list, C = 1):
    rdm_pallete = randomizeList(enumerate(pallete_list))
    rdm_source = randomizeList(enumerate(source_list))
    num_pixels = len(rdm_pallete)
    real_mapping = [0] * num_pixels

    chunk_size = int(num_pixels / C)

    chunked_rdm_pallete = chunks(rdm_pallete, chunk_size)
    chunked_rdm_source = chunks(rdm_source, chunk_size)
    zipped_chunks = zip(chunked_rdm_pallete, chunked_rdm_source)

    pool = mp.Pool(2)
    mappings = pool.map(getPartialMapping, zipped_chunks)

    for mapping, zipped_chunk in zip(mappings, zipped_chunks):
        pallete_chunk = zipped_chunk[0]
        source_chunk = zipped_chunk[1]
        for idx1,idx2 in enumerate(mapping):
            src_px = source_chunk[idx1]
            pal_px = pallete_chunk[idx2]
            real_mapping[src_px[0]] = pal_px[0]

    return real_mapping

def run(pallete_name, source_name, output_name):
    print("Getting Colors...")
    pallete_list = imageToColorList(pallete_name)
    source_list = imageToColorList(source_name)

    print("Creating Mapping...")
    mapping = getMappingWithPartitions(pallete_list, source_list, C = 16)

    print("Generating Image...");
    colorListToImage(pallete_list, source_name, output_name, mapping)

if __name__ == '__main__':
    pallete_name = sys.argv[1]
    source_name = sys.argv[2]
    output_name = sys.argv[3]
    run(pallete_name, source_name, output_name)

Wyniki:

Podobnie jak w przypadku rozwiązania aditsu, wszystkie te obrazy zostały wygenerowane przy użyciu dokładnie tych samych parametrów. Jedynym parametrem jest tutaj C, które powinno być ustawione tak nisko, jak to możliwe. Dla mnie C = 16 było dobrą równowagą między szybkością a jakością.

Wszystkie obrazy: http://imgur.com/a/RCZiX#0

Paleta gotycka w stylu amerykańskim

Paleta Mona Lisa

Paleta Gwiaździsta noc

Paleta krzyków

Paleta rzeki

Paleta kulek

Pyton

Edycja: Właśnie zdałem sobie sprawę, że możesz wyostrzyć źródło za pomocą ImageFilter, aby wyniki były lepiej zdefiniowane.

Tęcza -> Mona Lisa (wyostrzone źródło Mona Lisa, tylko Luminancja)

Tęcza -> Mona Lisa (źródło nieostrzone, ważone Y = 10, I = 10, Q = 0)

Mona Lisa -> American Gothic (źródło nieostrzone, tylko Luminancja)

Mona Lisa -> American Gothic (źródło nieostrzone, ważone Y = 1, I = 10, Q = 1)

Rzeka -> Tęcza (źródło nieostrzone, tylko luminancja)

Zasadniczo dzieli wszystkie piksele z dwóch zdjęć na dwie listy.

Sortuj je według luminancji jako klucza. Y w YIQ oznacza luminancję.

Następnie dla każdego piksela w źródle (w rosnącej kolejności luminancji) uzyskaj wartość RGB z piksela o tym samym indeksie na liście palet.

import Image, ImageFilter, colorsys

def getPixels(image):
    width, height = image.size
    pixels = []
    for x in range(width):
        for y in range(height):
            pixels.append([(x,y), image.getpixel((x,y))])
    return pixels

def yiq(pixel):
    # y is the luminance
    y,i,q = colorsys.rgb_to_yiq(pixel[1][0], pixel[1][6], pixel[1][7])
    # Change the weights accordingly to get different results
    return 10*y + 0*i + 0*q

# Open the images
source  = Image.open('ml.jpg')
pallete = Image.open('rainbow.png')

# Sharpen the source... It won't affect the palette anyway =D
source = source.filter(ImageFilter.SHARPEN)

# Sort the two lists by luminance
sourcePixels  = sorted(getPixels(source),  key=yiq)
palletePixels = sorted(getPixels(pallete), key=yiq)

copy = Image.new('RGB', source.size)

# Iterate through all the coordinates of source
# And set the new color
index = 0
for sourcePixel in sourcePixels:
    copy.putpixel(sourcePixel[0], palletePixels[index][8])
    index += 1

# Save the result
copy.save('copy.png')

Aby nadążać za trendem animacji ...

Piksele w krzyku są szybko dzielone na gwiaździstą noc i na odwrót

C # Winform - Visual Studio 2010

Dodano opcję Edycja ditheringu.

To moja wersja algorytmu wymiany losowej - @hobbs flavour. Nadal uważam, że jakiś przypadkowy dithering może zrobić lepiej ...

Opracowanie kolorów w przestrzeni Y-Cb-Cr (jak w kompresji jpeg)

Opracowanie dwufazowe:

1. Kopia piksela ze źródła w kolejności luminancji. To już daje dobry obraz, ale pozbawiony nasycenia - prawie szarą skalę - w czasie prawie zerowym
2. Powtarzana losowa zamiana pikseli. Zamiana jest wykonywana, jeśli daje to lepszą deltę (względem źródła) w komórce 3x3 zawierającej piksel. To efekt ditheringu. Delta jest obliczana na przestrzeni Y-Cr-Cb bez ważenia różnych składników.

Jest to w zasadzie ta sama metoda stosowana przez @hobbs, bez pierwszej losowej zamiany bez ditheringu. Po prostu moje czasy są krótsze (język się liczy?) I myślę, że moje obrazy są lepsze (prawdopodobnie zastosowana przestrzeń kolorów jest dokładniejsza).

Użycie programu: umieść obrazy .png w folderze c: \ temp, zaznacz element na liście, aby wybrać obraz palety, wybierz element z listy, aby wybrać obraz źródłowy (niezbyt przyjazny dla użytkownika). Kliknij przycisk Start, aby rozpocząć opracowywanie, zapisywanie jest automatyczne (nawet jeśli wolisz nie - uważaj).

Czas opracowania poniżej 90 sekund.

Zaktualizowane wyniki

Paleta: amerykański gotyk

Paleta: Monna Lisa

Paleta: Rainbow

Paleta: rzeka

Paleta: krzyk

Paleta: Gwiaździsta noc

Form1.cs

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Drawing.Imaging;
using System.IO;

namespace Palette
{
    public struct YRB
    {
        public int y, cb, cr;

        public YRB(int r, int g, int b)
        {
            y = (int)(0.299 * r + 0.587 * g + 0.114 * b);
            cb = (int)(128 - 0.168736 * r - 0.331264 * g + 0.5 * b);
            cr = (int)(128 + 0.5 * r - 0.418688 * g - 0.081312 * b);
        }
    }

    public struct Pixel
    {
        private const int ARGBAlphaShift = 24;
        private const int ARGBRedShift = 16;
        private const int ARGBGreenShift = 8;
        private const int ARGBBlueShift = 0;

        public int px, py;
        private uint _color;
        public YRB yrb;

        public Pixel(uint col, int px = 0, int py = 0)
        {
            this.px = px;
            this.py = py;
            this._color = col;
            yrb = new YRB((int)(col >> ARGBRedShift) & 255, (int)(col >> ARGBGreenShift) & 255, (int)(col >> ARGBBlueShift) & 255); 
        }

        public uint color
        {
            get { 
                return _color; 
            }
            set {
                _color = color;
                yrb = new YRB((int)(color >> ARGBRedShift) & 255, (int)(color >> ARGBGreenShift) & 255, (int)(color >> ARGBBlueShift) & 255);
            }
        }

        public int y
        {
            get { return yrb.y; }
        }
        public int cr
        {
            get { return yrb.cr; }
        }
        public int cb
        {
            get { return yrb.cb; }
        }
    }

    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            DirectoryInfo di = new System.IO.DirectoryInfo(@"c:\temp\");
            foreach (FileInfo file in di.GetFiles("*.png"))
            {
                ListViewItem item = new ListViewItem(file.Name);
                item.SubItems.Add(file.FullName);
                lvFiles.Items.Add(item);
            }
        }

        private void lvFiles_ItemSelectionChanged(object sender, ListViewItemSelectionChangedEventArgs e)
        {
            if (e.IsSelected)
            {
                string file = e.Item.SubItems[1].Text;
                GetImagePB(pbSource, file);
                pbSource.Tag = file; 
                DupImage(pbSource, pbOutput);

                this.Width = pbOutput.Width + pbOutput.Left + 20;
                this.Height = Math.Max(pbOutput.Height, pbPalette.Height)+lvFiles.Height*2;   
            }
        }

        private void lvFiles_ItemCheck(object sender, ItemCheckEventArgs e)
        {
            foreach (ListViewItem item in lvFiles.CheckedItems)
            {
                if (item.Index != e.Index) item.Checked = false;
            }
            string file = lvFiles.Items[e.Index].SubItems[1].Text;
            GetImagePB(pbPalette, file);
            pbPalette.Tag = lvFiles.Items[e.Index].SubItems[0].Text; 

            this.Width = pbOutput.Width + pbOutput.Left + 20;
            this.Height = Math.Max(pbOutput.Height, pbPalette.Height) + lvFiles.Height * 2;   
        }

        Pixel[] Palette;
        Pixel[] Source;

        private void BtnStart_Click(object sender, EventArgs e)
        {
            lvFiles.Enabled = false;
            btnStart.Visible = false;
            progressBar.Visible = true; 
            DupImage(pbSource, pbOutput);

            Work(pbSource.Image as Bitmap, pbPalette.Image as Bitmap, pbOutput.Image as Bitmap);

            string newfile = (string)pbSource.Tag +"-"+ (string)pbPalette.Tag;
            pbOutput.Image.Save(newfile, ImageFormat.Png);   

            lvFiles.Enabled = true;
            btnStart.Visible = true;
            progressBar.Visible = false;
        }

        private void Work(Bitmap srcb, Bitmap palb, Bitmap outb)
        {
            GetData(srcb, out Source);
            GetData(palb, out Palette);

            FastBitmap fout = new FastBitmap(outb);
            FastBitmap fsrc = new FastBitmap(srcb);
            int pm = Source.Length;
            int w = outb.Width;
            int h = outb.Height;
            progressBar.Maximum = pm;

            fout.LockImage();
            for (int p = 0; p < pm; p++)
            {
                fout.SetPixel(Source[p].px, Source[p].py, Palette[p].color);
            }
            fout.UnlockImage();

            pbOutput.Refresh();

            var rnd = new Random();
            int totsw = 0;
            progressBar.Maximum = 200;
            for (int i = 0; i < 200; i++)
            {
                int nsw = 0;
                progressBar.Value = i;
                fout.LockImage();
                fsrc.LockImage();
                for (int j = 0; j < 200000; j++)
                {
                    nsw += CheckSwap(fsrc, fout, 1 + rnd.Next(w - 2), 1 + rnd.Next(h - 2), 1 + rnd.Next(w - 2), 1 + rnd.Next(h - 2));
                }
                totsw += nsw;
                lnCurSwap.Text = nsw.ToString();
                lnTotSwap.Text = totsw.ToString();
                fout.UnlockImage();
                fsrc.UnlockImage();
                pbOutput.Refresh();
                Application.DoEvents();
                if (nsw == 0)
                {
                    break;
                }
            }            
        }

        int CheckSwap(FastBitmap fsrc, FastBitmap fout, int x1, int y1, int x2, int y2)
        {
            const int fmax = 3;
            YRB ov1 = new YRB();
            YRB sv1 = new YRB();
            YRB ov2 = new YRB();
            YRB sv2 = new YRB();

            int f;
            for (int dx = -1; dx <= 1; dx++)
            {
                for (int dy = -1; dy <= 1; dy++)
                {
                    f = (fmax - Math.Abs(dx) - Math.Abs(dy));
                    {
                        Pixel o1 = new Pixel(fout.GetPixel(x1 + dx, y1 + dy));
                        ov1.y += o1.y * f;
                        ov1.cb += o1.cr * f;
                        ov1.cr += o1.cb * f;

                        Pixel s1 = new Pixel(fsrc.GetPixel(x1 + dx, y1 + dy));
                        sv1.y += s1.y * f;
                        sv1.cb += s1.cr * f;
                        sv1.cr += s1.cb * f;

                        Pixel o2 = new Pixel(fout.GetPixel(x2 + dx, y2 + dy));
                        ov2.y += o2.y * f;
                        ov2.cb += o2.cr * f;
                        ov2.cr += o2.cb * f;

                        Pixel s2 = new Pixel(fsrc.GetPixel(x2 + dx, y2 + dy));
                        sv2.y += s2.y * f;
                        sv2.cb += s2.cr * f;
                        sv2.cr += s2.cb * f;
                    }
                }
            }
            YRB ox1 = ov1;
            YRB ox2 = ov2;
            Pixel oc1 = new Pixel(fout.GetPixel(x1, y1));
            Pixel oc2 = new Pixel(fout.GetPixel(x2, y2));
            ox1.y += fmax * oc2.y - fmax * oc1.y;
            ox1.cb += fmax * oc2.cr - fmax * oc1.cr;
            ox1.cr += fmax * oc2.cb - fmax * oc1.cb;
            ox2.y += fmax * oc1.y - fmax * oc2.y;
            ox2.cb += fmax  * oc1.cr - fmax * oc2.cr;
            ox2.cr += fmax * oc1.cb - fmax * oc2.cb;

            int curd = Delta(ov1, sv1, 1) + Delta(ov2, sv2, 1);
            int newd = Delta(ox1, sv1, 1) + Delta(ox2, sv2, 1);
            if (newd < curd)
            {
                fout.SetPixel(x1, y1, oc2.color);
                fout.SetPixel(x2, y2, oc1.color);
                return 1;
            }
            return 0;
        }

        int Delta(YRB p1, YRB p2, int sf)
        {
            int dy = (p1.y - p2.y);
            int dr = (p1.cr - p2.cr);
            int db = (p1.cb - p2.cb);

            return dy * dy * sf + dr * dr + db * db;
        }

        Bitmap GetData(Bitmap bmp, out Pixel[] Output)
        {
            FastBitmap fb = new FastBitmap(bmp);
            BitmapData bmpData = fb.LockImage(); 

            Output = new Pixel[bmp.Width * bmp.Height];

            int p = 0;
            for (int y = 0; y < bmp.Height; y++)
            {
                uint col = fb.GetPixel(0, y);
                Output[p++] = new Pixel(col, 0, y);

                for (int x = 1; x < bmp.Width; x++)
                {
                    col = fb.GetNextPixel();
                    Output[p++] = new Pixel(col, x, y);
                }
            }
            fb.UnlockImage(); // Unlock the bits.

            Array.Sort(Output, (a, b) => a.y - b.y);

            return bmp;
        }

        void DupImage(PictureBox s, PictureBox d)
        {
            if (d.Image != null)
                d.Image.Dispose();
            d.Image = new Bitmap(s.Image.Width, s.Image.Height);  
        }

        void GetImagePB(PictureBox pb, string file)
        {
            Bitmap bms = new Bitmap(file, false);
            Bitmap bmp = bms.Clone(new Rectangle(0, 0, bms.Width, bms.Height), PixelFormat.Format32bppArgb);
            bms.Dispose(); 
            if (pb.Image != null)
                pb.Image.Dispose();
            pb.Image = bmp;
        }
    }

    //Adapted from Visual C# Kicks - http://www.vcskicks.com/
    unsafe public class FastBitmap
    {
        private Bitmap workingBitmap = null;
        private int width = 0;
        private BitmapData bitmapData = null;
        private Byte* pBase = null;

        public FastBitmap(Bitmap inputBitmap)
        {
            workingBitmap = inputBitmap;
        }

        public BitmapData LockImage()
        {
            Rectangle bounds = new Rectangle(Point.Empty, workingBitmap.Size);

            width = (int)(bounds.Width * 4 + 3) & ~3;

            //Lock Image
            bitmapData = workingBitmap.LockBits(bounds, ImageLockMode.ReadWrite, PixelFormat.Format32bppArgb);
            pBase = (Byte*)bitmapData.Scan0.ToPointer();
            return bitmapData;
        }

        private uint* pixelData = null;

        public uint GetPixel(int x, int y)
        {
            pixelData = (uint*)(pBase + y * width + x * 4);
            return *pixelData;
        }

        public uint GetNextPixel()
        {
            return *++pixelData;
        }

        public void GetPixelArray(int x, int y, uint[] Values, int offset, int count)
        {
            pixelData = (uint*)(pBase + y * width + x * 4);
            while (count-- > 0)
            {
                Values[offset++] = *pixelData++;
            }
        }

        public void SetPixel(int x, int y, uint color)
        {
            pixelData = (uint*)(pBase + y * width + x * 4);
            *pixelData = color;
        }

        public void SetNextPixel(uint color)
        {
            *++pixelData = color;
        }

        public void UnlockImage()
        {
            workingBitmap.UnlockBits(bitmapData);
            bitmapData = null;
            pBase = null;
        }
    }

}