Skip to content

Reproduire une image à l'aide de lignes

N'hésitez pas à partager notre site et nos codes avec d'autres, nous avons besoin de votre aide pour élargir cette communauté.

Solution :

C++ - des lignes quelque peu aléatoires et d'autres encore

D'abord quelques lignes aléatoires

La première étape de l'algorithme génère aléatoirement des lignes, prend pour l'image cible une moyenne des pixels le long de celle-ci, puis calcule si le carré additionné des distances de l'espace rgb de tous les pixels serait plus faible si nous peignons la nouvelle ligne (et ne la peint que si c'est le cas). La couleur des nouvelles lignes pour cela est choisie comme la moyenne par canal des valeurs rgb, avec une addition aléatoire de -15/+15.

Des choses que j'ai remarquées et qui ont influencé l'implémentation :

  • La couleur initiale est la moyenne de l'image complète. C'est pour contrer des effets amusants comme quand on la rend blanche, et que la zone est noire, alors déjà quelque chose comme une ligne verte brillante est mieux vue, car elle est plus proche du noir que celle déjà blanche.
  • Prendre la couleur moyenne pure pour la ligne n'est pas si bonne car il s'avère qu'elle ne peut pas générer de surbrillance en étant écrasée par les lignes ultérieures. Faire une petite déviation aléatoire aide un peu, mais si vous regardez la nuit étoilée, cela échoue si le contraste local est élevé à de nombreux endroits.

J'ai expérimenté avec quelques chiffres, et j'ai choisi... L=0.3*pixel_count(I) et laissé m=10 et M=50. Il produira de beaux résultats à partir d'environ 0.25 jusqu'à 0.26 pour le nombre de lignes, mais j'ai choisi 0,3 pour avoir plus de place pour des détails précis.

Pour l'image de la porte d'or en taille réelle, cela a donné 235929 lignes à peindre (pour lesquelles il a fallu un énorme 13 secondes ici). Notez que toutes les images ici sont affichées en taille réduite et que vous devez les ouvrir dans un nouvel onglet/les télécharger pour voir la pleine résolution.

Effacer l'indigne

L'étape suivante est plutôt coûteuse (pour les 235k lignes, cela a pris environ une heure, mais cela devrait être bien dans les limites du temps requis "une heure pour 10k lignes sur 1 mégapixel"), mais elle est aussi un peu surprenante. Je passe en revue toutes les lignes précédemment peintes, et j'enlève celles qui n'améliorent pas l'image. Cela me laisse dans ce run avec seulement 97347 lignes qui produisent l'image suivante :

Vous devez probablement les télécharger et les comparer dans un visualiseur d'images approprié pour repérer la plupart des différences.

et recommencer à nouveau

Maintenant, j'ai beaucoup de lignes que je peux peindre à nouveau pour avoir un total de 235929 à nouveau. Pas grand chose à dire, alors voici l'image :

Entrez la description de l'image ici

courte analyse

Toute la procédure semble fonctionner comme un filtre flou sensible au contraste local et à la taille des objets. Mais il est aussi intéressant de voir où sont peintes les lignes, donc le programme les enregistre aussi (Pour chaque ligne, la couleur du pixel sera rendue un pas plus blanche, à la fin le contraste est maximisé). Voici celles qui correspondent aux trois colorées ci-dessus.

animations

Et puisque nous aimons tous les animations, voici quelques gifs animés de l'ensemble du processus pour l'image plus petite du golden gate. Notez qu'il y a un dithering significatif dû au format gif (et comme les créateurs de formats de fichiers d'animation en couleurs vraies et les fabricants de navigateurs sont en guerre pour leurs égos, il n'y a pas de format standard pour les animations en couleurs vraies, sinon j'aurais pu ajouter un .mng ou similaire).

Un peu plus

Comme demandé, voici quelques résultats des autres images (encore une fois, vous devrez peut-être les ouvrir dans un nouvel onglet pour ne pas les avoir réduites).

Réflexions futures

Jouer avec le code peut donner des variations intéressantes.

  • Choisir la couleur des lignes au hasard au lieu de se baser sur la moyenne. Vous pourriez avoir besoin de plus de deux cycles.
  • Le code dans le pastebin contient également une certaine idée d'un algorithme génétique, mais l'image est probablement déjà si bonne qu'il faudrait trop de générations, et ce code est également trop lent pour entrer dans la règle "une heure".
  • Faire un autre tour d'effacement/peinture, ou même deux....
  • Modifier la limite de l'endroit où les lignes peuvent être effacées (par exemple, "doit rendre l'image au moins N meilleure").

Le code

Ce ne sont que les deux principales fonctions utiles, l'ensemble du code n'a pas sa place ici et se trouve sur http://ideone.com/Z2P6Ls.

Le site bmp classes raw et raw_line permettent d'accéder aux pixels et aux lignes respectivement dans un objet qui peut être écrit au format bmp. (C'était juste un hack qui traînait et je pensais que cela rendait cela quelque peu indépendant de toute bibliothèque).

Le format du fichier d'entrée est PPM

std::pair>  paint_useful( const bmp& orig, bmp& clone, std::vector& retlines, bmp& layer, const std::string& outprefix, size_t x, size_t y )
{
        const size_t pixels = (x*y);
        const size_t lines = 0.3*pixels;
//      const size_t lines = 10000;

//      const size_t start_accurate_color = lines/4;

        std::random_device rnd;

        std::uniform_int_distribution distx(0,x-1);
        std::uniform_int_distribution disty(0,y-1);
        std::uniform_int_distribution col(-15,15);
        std::uniform_int_distribution acol(0,255);

        const ssize_t m = 1*1;
        const ssize_t M = 50*50;

        retlines.reserve( lines );

        for (size_t i = retlines.size(); i < lines; ++i)
        {
                size_t x0;
                size_t x1;

                size_t y0;
                size_t y1;

                size_t dist = 0;
                do
                {
                        x0 = distx(rnd);
                        x1 = distx(rnd);

                        y0 = disty(rnd);
                        y1 = disty(rnd);

                        dist = distance(x0,x1,y0,y1);
                }
                while( dist > M || dist < m );

                std::vector> points = clone.raw_line_pixels(x0,y0,x1,y1);

                ssize_t r = 0;
                ssize_t g = 0;
                ssize_t b = 0;

                for (size_t i = 0; i < points.size(); ++i)
                {
                        r += orig.raw(points[i].first,points[i].second).r;
                        g += orig.raw(points[i].first,points[i].second).g;
                        b += orig.raw(points[i].first,points[i].second).b;
                }

                r += col(rnd);
                g += col(rnd);
                b += col(rnd);

                r /= points.size();
                g /= points.size();
                b /= points.size();

                r %= 255;
                g %= 255;
                b %= 255;

                r = std::max(ssize_t(0),r);
                g = std::max(ssize_t(0),g);
                b = std::max(ssize_t(0),b);

//              r = acol(rnd);
//              g = acol(rnd);
//              b = acol(rnd);

//              if( i > start_accurate_color )
                {
                        ssize_t dp = 0; // accumulated distance of new color to original
                        ssize_t dn = 0; // accumulated distance of current reproduced to original
                        for (size_t i = 0; i < points.size(); ++i)
                        {
                                dp += rgb_distance(
                                                                                orig.raw(points[i].first,points[i].second).r,r,
                                                                                orig.raw(points[i].first,points[i].second).g,g,
                                                                                orig.raw(points[i].first,points[i].second).b,b
                                                                        );

                                dn += rgb_distance(
                                                                                clone.raw(points[i].first,points[i].second).r,orig.raw(points[i].first,points[i].second).r,
                                                                                clone.raw(points[i].first,points[i].second).g,orig.raw(points[i].first,points[i].second).g,
                                                                                clone.raw(points[i].first,points[i].second).b,orig.raw(points[i].first,points[i].second).b
                                                                        );

                        }

                        if( dp > dn ) // the distance to original is bigger, use the new one
                        {
                                --i;
                                continue;
                        }
                        // also abandon if already too bad
//                      if( dp > 100000 )
//                      {
//                              --i;
//                              continue;
//                      }
                }

                layer.raw_line_add(x0,y0,x1,y1,{1u,1u,1u});
                clone.raw_line(x0,y0,x1,y1,{(uint32_t)r,(uint32_t)g,(uint32_t)b});
                retlines.push_back({ (int)x0,(int)y0,(int)x1,(int)y1,(int)r,(int)g,(int)b});

                static time_t last = 0;
                time_t now = time(0);
                if( i % (lines/100) == 0 )
                {
                        std::ostringstream fn;
                        fn << outprefix + "perc_" << std::setw(3) << std::setfill('0') << (i/(lines/100)) << ".bmp"; 
                        clone.write(fn.str());
                        bmp lc(layer);
                        lc.max_contrast_all();
                        lc.write(outprefix + "layer_" + fn.str());
                }

                if( (now-last) > 10 )
                {
                        last = now;
                        static int st = 0;
                        std::ostringstream fn;
                        fn << outprefix + "inter_" << std::setw(8) << std::setfill('0') << i << ".bmp";
                        clone.write(fn.str());

                        ++st;
                }
        }
        clone.write(outprefix + "clone.bmp");
        return { clone, retlines };
}

void erase_bad( std::vector& lines, const bmp& orig )
{
        ssize_t current_score = evaluate(lines,orig);

        std::vector newlines(lines);

        uint32_t deactivated = 0;
        std::cout << "current_score = " << current_score << "n";
        for (size_t i = 0; i < newlines.size(); ++i)
        {
                newlines[i].active = false;
                ssize_t score = evaluate(newlines,orig);
                if( score > current_score )
                {
                        newlines[i].active = true;
                }
                else
                {
                        current_score = score;
                        ++deactivated;
                }
                if( i % 1000 == 0 )
                {
                        std::ostringstream fn;
                        fn << "erase_" << std::setw(6) << std::setfill('0') << i << ".bmp";
                        bmp tmp(orig);
                        paint(newlines,tmp);
                        tmp.write(fn.str());
                        paint_layers(newlines,tmp);
                        tmp.max_contrast_all();
                        tmp.write("layers_" + fn.str());
                        std::cout << "r i = " << i << std::flush;
                }
        }
        std::cout << "n";
        std::cout << "current_score = " << current_score << "n";
        std::cout << "deactivated = " << deactivated << "n";

        bmp tmp(orig);

        paint(newlines,tmp);
        tmp.write("newlines.bmp");
        lines.clear();
        for (size_t i = 0; i < newlines.size(); ++i)
        {
                if( newlines[i].is_active() )
                {
                        lines.push_back(newlines[i]);
                }
        }
}

Java - lignes aléatoires

Une solution très basique qui dessine des lignes aléatoires et calcule pour elles la couleur moyenne de l'image source. La couleur de fond est fixée à la couleur moyenne de la source.

L = 5000, m = 10, M = 50

Entrez la description de l'image ici

L = 10000, m = 10, M = 50

Entrez la description de l'image ici

EDIT

J'ai ajouté un algorithme génétique qui gère une population de lignes. A chaque génération, on ne garde que les 50% de meilleures lignées, on laisse tomber les autres et on en génère de nouvelles de façon aléatoire.
Les critères pour garder les lignes sont :

  • leur distance aux couleurs de l'image source est faible
  • le nombre d'intersections avec d'autres lignes (plus il est petit, mieux c'est)
  • leur longueur (plus elle est longue, mieux c'est)
  • leur angle avec le voisin le plus proche (plus il est petit, mieux c'est)

A ma grande déception, l'algorithme ne semble pas vraiment améliorer la qualité de l'image 🙁 juste les lignes deviennent plus parallèles.

Première génération (5000 lignes)

Entrez la description de l'image ici

Dixième génération (5000 lignes)

Entrez la description de l'image ici

Jouer avec les paramètres

Entrez la description de l'image iciEntrez la description de l'image iciEntrez la description de l'image ici

package line;

import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import javax.imageio.ImageIO;

import snake.Image;

public class Lines {

    private final static int NB_LINES = 5000;
    private final static int MIN_LENGTH = 10;
    private final static int MAX_LENGTH = 50;

    public static void main(String[] args) throws IOException {     
        BufferedImage src = ImageIO.read(Image.class.getClassLoader().getResourceAsStream("joconde.png"));
        BufferedImage dest = new BufferedImage(src.getWidth(), src.getHeight(), BufferedImage.TYPE_INT_RGB);

        int [] bgColor = {0, 0, 0};
        int avgRed = 0, avgGreen = 0, avgBlue = 0, count = 0;
        for (int y = 0; y < src.getHeight(); y++) {
            for (int x = 0; x < src.getWidth(); x++) {
                int colsrc = src.getRGB(x, y);
                avgRed += colsrc & 255;
                avgGreen += (colsrc >> 8) & 255;
                avgBlue += (colsrc >> 16) & 255;
                count++;
            }
        }

        bgColor[0] = avgBlue/count; bgColor[1] = avgGreen/count; bgColor[2] = avgRed/count;
        for (int y = 0; y < src.getHeight(); y++) {
            for (int x = 0; x < src.getWidth(); x++) {
                dest.getRaster().setPixel(x, y, bgColor);
            }
        }
        List> lines = new ArrayList>();
        Random rand = new Random();
        for (int i = 0; i < NB_LINES; i++) {
            int length = rand.nextInt(MAX_LENGTH - MIN_LENGTH) + MIN_LENGTH;
            double ang = rand.nextDouble() * Math.PI;
            int lx = (int)(Math.cos(ang) * length); // can be negative or positive
            int ly = (int)(Math.sin(ang) * length); // positive only
            int sx = rand.nextInt(dest.getWidth() -1 - Math.abs(lx));
            int sy = rand.nextInt(dest.getHeight() - 1- Math.abs(ly));
            List line;
            if (lx > 0) {
                line = line(sx, sy, sx+lx, sy+ly);
            } else {
                line = line(sx+Math.abs(lx), sy, sx, sy+ly);
            }
            lines.add(line);    
        }

        // render the picture
        int [] color = {0, 0, 0};
        for (List line : lines) {

            avgRed = 0; avgGreen = 0; avgBlue = 0;
            count = 0;
            for (Point p : line) {
                int colsrc = src.getRGB(p.x, p.y);
                avgRed += colsrc & 255;
                avgGreen += (colsrc >> 8) & 255;
                avgBlue += (colsrc >> 16) & 255;
                count++;
            }
            avgRed /= count; avgGreen /= count; avgBlue /= count;
            color[0] = avgBlue; color[1] = avgGreen; color[2] = avgRed;
            for (Point p : line) {
                dest.getRaster().setPixel(p.x, p.y, color);
            }

        }
        ImageIO.write(dest, "png", new File("a0.png"));

    }

    private static List line(int x0, int y0, int x1, int y1) {
        List points = new ArrayList();
        int deltax = x1 - x0;
        int deltay = y1 - y0;
        int tmp;
        double error = 0;       
        double deltaerr = 0;
        if (Math.abs(deltax) >= Math.abs(deltay)) {
            if (x0 > x1) { // swap the 2 points
                tmp = x0; x0 = x1; x1 = tmp;
                tmp = y0; y0 = y1; y1 = tmp;
                deltax = - deltax; deltay = -deltay;
            }
            deltaerr = Math.abs (((double)deltay) / deltax); 
            int y = y0;
            for (int x = x0; x <= x1; x++) {
                points.add(new Point(x, y));
                error += deltaerr;
                if (error >= 0.5) {
                    if (y0 < y1) y++; else y--;
                    error -= 1.0;
                }
            }
        } else {
            if (y0 > y1) { // swap the 2 points
                tmp = x0; x0 = x1; x1 = tmp;
                tmp = y0; y0 = y1; y1 = tmp;
                deltax = - deltax; deltay = -deltay;
            }
            deltaerr = Math.abs (((double)deltax) / deltay);   // Assume deltay != 0 (line is not horizontal),
            int x = x0;
            for (int y = y0; y <= y1; y++) {
                points.add(new Point(x, y));
                error += deltaerr;
                if (error >= 0.5) {
                    if (x0 < x1) x++; else x--;
                    error -= 1.0;
                }
            }
        }
        return points;
    }
}

C - lignes droites

Une approche de base en C qui opère sur des fichiers ppm. L'algorithme essaie de placer des lignes verticales avec une longueur de ligne optimale pour remplir tous les pixels. La couleur de fond et les couleurs des lignes sont calculées comme une valeur moyenne de l'image originale (la médiane de chaque canal de couleur) :

#include 
#include 
#include 

#define SIGN(x) ((x > 0) ? 1 : (x < 0) ? -1 : 0)
#define MIN(x, y) ((x > y) ? y : x)
#define MAX(x, y) ((x > y) ? x : y)

typedef struct {
    size_t width;
    size_t height;

    unsigned char *r;
    unsigned char *g;
    unsigned char *b;
} image;

typedef struct {
    unsigned char r;
    unsigned char g;
    unsigned char b;
} color;

void init_image(image *data, size_t width, size_t height) {
    data->width = width;
    data->height = height;
    data->r = malloc(sizeof(data->r) * data->width * data->height);
    data->g = malloc(sizeof(data->g) * data->width * data->height);
    data->b = malloc(sizeof(data->b) * data->width * data->height);
}

#define BUFFER_LEN 1024
int load_image(const char *filename, image* data) {
    FILE *f = fopen(filename, "r");
    char buffer[BUFFER_LEN];          /* read buffer */
    size_t max_value;
    size_t i;
    fgets(buffer, BUFFER_LEN, f);
    if (strncmp(buffer, "P3", 2) != 0) {
        printf("File begins with %s instead of P3n", buffer);
        return 0;
    }

    fscanf(f, "%u", &data->width);
    fscanf(f, "%u", &data->height);
    fscanf(f, "%u", &max_value);
    assert(max_value==255);

    init_image(data, data->width, data->height);

    for (i = 0; i < data->width * data->height; i++) {
        fscanf(f, "%hhu", &(data->r[i]));
        fscanf(f, "%hhu", &(data->g[i]));
        fscanf(f, "%hhu", &(data->b[i]));
    }
    fclose(f);

    printf("Read %zux%zu pixels from %s.n", data->width, data->height, filename);
}

int write_image(const char *filename, image *data) {
    FILE *f = fopen(filename, "w");
    size_t i;
    fprintf(f, "P3n%zu %zun255n", data->width, data->height);
    for (i = 0; i < data->width * data->height; i++) {
        fprintf(f, "%hhu %hhu %hhu ", data->r[i], data->g[i], data->b[i]);
    }
    fclose(f);
}

unsigned char average(unsigned char *data, size_t data_len) {
    size_t i;
    size_t j;
    size_t hist[256];

    for (i = 0; i < 256; i++) hist[i] = 0;
    for (i = 0; i < data_len; i++) hist[data[i]]++;
    j = 0;
    for (i = 0; i < 256; i++) {
        j += hist[i];
        if (j >= data_len / 2) return i;
    }
    return 255;
}

void set_pixel(image *data, size_t x, size_t y, unsigned char r, unsigned char g, unsigned char b) {
    data->r[x + data->width * y] = r;
    data->g[x + data->width * y] = g;
    data->b[x + data->width * y] = b;
}

color get_pixel(image *data, size_t x, size_t y) {
    color ret;
    ret.r = data->r[x + data->width * y];
    ret.g = data->g[x + data->width * y];
    ret.b = data->b[x + data->width * y];
    return ret;
}

void fill(image *data, unsigned char r, unsigned char g, unsigned char b) {
    size_t i;
    for (i = 0; i < data->width * data->height; i++) {
        data->r[i] = r;
        data->g[i] = g;
        data->b[i] = b;
    }
}

void line(image *data, size_t x1, size_t y1, size_t x2, size_t y2, unsigned char r, unsigned char g, unsigned char b) {
    size_t x, y, t, pdx, pdy, ddx, ddy, es, el;
    int dx, dy, incx, incy, err;

    dx=x2-x1;
    dy=y2-y1;
    incx=SIGN(dx);
    incy=SIGN(dy);
    if(dx<0) dx=-dx;
    if(dy<0) dy=-dy;
    if (dx>dy) {
        pdx=incx;
        pdy=0;
        ddx=incx;
        ddy=incy;
        es=dy;
        el=dx;
    } else {
        pdx=0;
        pdy=incy;
        ddx=incx;
        ddy=incy;
        es=dx;
        el=dy;
    }
    x=x1;
    y=y1;
    err=el/2;
    set_pixel(data, x, y, r, g, b);

    for(t=0; tdy) {
        pdx=incx;
        pdy=0;
        ddx=incx;
        ddy=incy;
        es=dy;
        el=dx;
    } else {
        pdx=0;
        pdy=incy;
        ddx=incx;
        ddy=incy;
        es=dx;
        el=dy;
    }
    x=x1;
    y=y1;
    err=el/2;
    px = get_pixel(data, x, y);
    hist_r[px.r]++;
    hist_g[px.g]++;
    hist_b[px.b]++;
    data_len++;

    for(t=0; t= data_len / 2) {
            ret.r = i;
            break;
        }
    }
    j = 0;
    for (i = 0; i < 256; i++) {
        j += hist_g[i];
        if (j >= data_len / 2) {
            ret.g = i;
            break;
        }
    }
    j = 0;
    for (i = 0; i < 256; i++) {
        j += hist_b[i];
        if (j >= data_len / 2) {
            ret.b = i;
            break;
        }
    }
    return ret;
}

void lines(image *source, image *dest, size_t L, float m, float M) {
    size_t i, j;
    float dx;
    float mx, my;
    float mm = MAX(MIN(source->width * source->height / L, M), m);
    unsigned char av_r = average(source->r, source->width * source->height);
    unsigned char av_g = average(source->g, source->width * source->height);
    unsigned char av_b = average(source->b, source->width * source->height);
    fill(dest, av_r, av_g, av_b);
    dx = (float)source->width / L;
    mx = 0;
    my = mm / 2;
    for (i = 0; i < L; i++) {
        color avg;
        mx += dx;
        my += (source->height - mm) / 8;
        if (my + mm / 2 > source->height) {
            my = mm / 2 + ((size_t)(my + mm / 2) % (size_t)(source->height - mm));
        }
        avg = average_line(source, mx, my - mm / 2, mx, my + mm / 2);
        line(dest, mx, my - mm / 2, mx, my + mm / 2, avg.r, avg.g, avg.b);
    }
}

int main(int argc, char *argv[]) {
    image source;
    image dest;
    size_t L;
    float m;
    float M;

    load_image(argv[1], &source);
    L = atol(argv[2]);
    m = atof(argv[3]);
    M = atof(argv[4]);

    init_image(&dest, source.width, source.height);
    lines(&source, &dest, L, m, M);

    write_image(argv[5], &dest);
}

L = 5000, m = 10, M = 50

L = 5000, m = 10, m = 50

L = 5000, m = 10, M = 50

L = 5000, m = 10, m = 50

L = 100000, m = 10, M = 50

Entrez la description de l'image ici

Si ce message vous a été utile, il serait très utile que vous le partagiez avec plus de programmeurs de cette manière, vous nous aidez à diffuser nos informations.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.