Überbrücken Sie die Lücken

14

Zeichnen Sie bei einem Schwarzweißbild mit weißem Hintergrund und einer Reihe schwarzer Punkte eine Reihe weißer Pixel rot, sodass zwischen jedem Paar schwarzer Pixel ein Pfad liegt.

Einzelheiten

  • Ein Pfad ist ein Satz verbundener Pixel (Konnektivität mit 8 Nachbarschaften). Schwarze Pixel können als Teil der Pfade verwendet werden. Das Ziel besteht darin, die Menge der roten Pixel unter den obigen Bedingungen zu minimieren und ein entsprechendes Bild auszugeben.

  • Sie müssen nicht müssen , die optimale Lösung zu finden.

  • Eine triviale und gleichzeitig schlechteste Lösung ist es, alle weißen Pixel rot zu malen.

  • Beispiel (Pixel werden zur besseren Sichtbarkeit vergrößert):

Einzelheiten

  • Bei einem gegebenen Pixelbild (in einem geeigneten Format) wird ein weiteres Bild mit den wie oben angegeben verbundenen Punkten sowie eine Ganzzahl zurückgegeben, die angibt, wie viele rote Pixel verwendet wurden.
  • Die Punktzahl ergibt sich aus (1 + Anzahl der roten Pixel) für jeden der 14 Testfälle.
  • Das Ziel ist die niedrigste Punktzahl.

Testfälle

Die 14 Testfälle sind unten gezeigt. Ein Python-Programm zum Überprüfen der Verbindung der Ausgänge finden Sie hier.

Meta

Vielen Dank an @Veskah, @Fatalize, @ wizzwizz4 und @trichoplax für die verschiedenen Vorschläge.

fehlerhaft
quelle
1
Gute Herausforderung; Ich mag solche mit verschiedenen und kreativen Bewertungsschemata. Ich gehe davon aus, dass das Programm an einem beliebigen Bild arbeiten muss, nicht nur an diesen 14 spezifischen Beispielen. Wenn ja, können wir eine vernünftige maximale Größe wie 512 x 512 pro Mona Lisa-Bild oder 1024 x 1024 annehmen?
BradC
Danke für die Rückmeldung! Ja, Sie können eine maximale Größe (bei Bedarf auch eine minimale Größe) annehmen, solange alle 14 Beispiele verarbeitet werden können.
Fehler
Wie konvertiere ich PNG in ASCII oder JSON oder etwas anderes, das einfach zu analysieren ist?
ngn
Müssen Sie in der Lage sein, Ihre eigene Punktzahl zu berechnen? Ein Programm, das jede mögliche Kombination von weißen Pixeln ausprobiert, um Rot zu malen, und feststellt, welche Teilmenge die wenigsten roten Pixel aufweist, während alle schwarzen Pixel verbunden werden, hätte die bestmögliche Punktzahl, wäre jedoch so langsam, dass es länger dauern würde als die Lebensdauer des Universums tatsächlich diese Punktzahl zu berechnen.
Leo Tenenbaum
1
@ngn In GIMP öffnen und als NetPBM-Format speichern.
wizzwizz4

Antworten:

7

C, Punktzahl 2.397 x 10 ^ 38

Mann, das hat viel zu lange gedauert, wahrscheinlich aufgrund meiner Sprachwahl. Ich habe den Algorithmus ziemlich früh zum Laufen gebracht, aber es gab viele Probleme mit der Speicherzuordnung (rekursives Freigeben von Daten aufgrund von Stapelüberläufen nicht möglich, Leckgrößen waren enorm).

Immer noch! Es schlägt den anderen Eintrag in jedem Testfall und kann sogar optimal sein, wenn es ziemlich nahe kommt oder genau optimale Lösungen.

Wie auch immer, hier ist der Code:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define WHITE 'W'
#define BLACK 'B'
#define RED   'R'


typedef struct image {
    int w, h;
    char* buf;
} image;

typedef struct point {
    int x, y;
    struct point *next;
    struct point *parent;
} point;

typedef struct shape {
    point* first_point;
    point* last_point;

    struct shape* next_shape;
} shape;


typedef struct storage {
    point* points;
    size_t points_size;
    size_t points_index;

    shape* shapes;
    size_t shapes_size;
    size_t shapes_index;
} storage;

char getpx(image* img, int x, int y) {
    if (0>x || x>=img->w || 0>y || y>=img->h) {
        return WHITE;
    } else {
        return img->buf[y*img->w+x];
    }
}

storage* create_storage(int w, int h) {
    storage* ps = (storage*)malloc(sizeof(storage));

    ps->points_size = 8*w*h;
    ps->points = (point*)calloc(ps->points_size, sizeof(point));
    ps->points_index = 0;

    ps->shapes_size = 2*w*h;
    ps->shapes = (shape*)calloc(ps->shapes_size, sizeof(shape));
    ps->shapes_index = 0;

    return ps;
}

void free_storage(storage* ps) {
    if (ps != NULL) {
        if (ps->points != NULL) {
            free(ps->points);
            ps->points = NULL;
        }
        if (ps->shapes != NULL) {
            free(ps->shapes);
            ps->shapes = NULL;
        }
        free(ps);
    }
}


point* alloc_point(storage* ps) {
    if (ps->points_index == ps->points_size) {
        printf("WHOAH THERE BUDDY SLOW DOWN\n");
        /*// double the size of the buffer
        point* new_buffer = (point*)malloc(ps->points_size*2*sizeof(point));
        // need to change all existing pointers to point to new buffer
        long long int pointer_offset = (long long int)new_buffer - (long long int)ps->points;
        for (size_t i=0; i<ps->points_index; i++) {
            new_buffer[i] = ps->points[i];
            if (new_buffer[i].next != NULL) {
                new_buffer[i].next += pointer_offset;
            }
            if (new_buffer[i].parent != NULL) {
                new_buffer[i].parent += pointer_offset;
            }
        }

        for(size_t i=0; i<ps->shapes_index; i++) {
            if (ps->shapes[i].first_point != NULL) {
                ps->shapes[i].first_point += pointer_offset;
            }
            if (ps->shapes[i].last_point != NULL) {
                ps->shapes[i].last_point += pointer_offset;
            }
        }

        free(ps->points);
        ps->points = new_buffer;
        ps->points_size = ps->points_size * 2;*/
    }
    point* out = &(ps->points[ps->points_index]);
    ps->points_index += 1;
    return out;
}

shape* alloc_shape(storage* ps) {
    /*if (ps->shapes_index == ps->shapes_size) {
        // double the size of the buffer
        shape* new_buffer = (shape*)malloc(ps->shapes_size*2*sizeof(shape));
        long long int pointer_offset = (long long int)new_buffer - (long long int)ps->shapes;
        for (size_t i=0; i<ps->shapes_index; i++) {
            new_buffer[i] = ps->shapes[i];
            if (new_buffer[i].next_shape != NULL) {
                new_buffer[i].next_shape += pointer_offset;
            }
        }
        free(ps->shapes);
        ps->shapes = new_buffer;
        ps->shapes_size = ps->shapes_size * 2;
    }*/
    shape* out = &(ps->shapes[ps->shapes_index]);
    ps->shapes_index += 1;
    return out;
}

shape floodfill_shape(image* img, storage* ps, int x, int y, char* buf) {
    // not using point allocator for exploration stack b/c that will overflow it

    point* stack = (point*)malloc(sizeof(point));
    stack->x = x;
    stack->y = y;
    stack->next = NULL;
    stack->parent = NULL;

    point* explored = NULL;
    point* first_explored;
    point* next_explored;

    while (stack != NULL) {
        int sx = stack->x;
        int sy = stack->y;
        point* prev_head = stack;
        stack = stack->next;
        free(prev_head);

        buf[sx+sy*img->w] = 1; // mark as explored

        // add point to shape
        next_explored = alloc_point(ps);
        next_explored->x = sx;
        next_explored->y = sy;
        next_explored->next = NULL;
        next_explored->parent = NULL;

        if (explored != NULL) {
            explored->next = next_explored;
        } else {
            first_explored = next_explored;
        }
        explored = next_explored;

        for (int dy=-1; dy<2; dy++) {
        for (int dx=-1; dx<2; dx++) {
            if (dy != 0 || dx != 0) {
                int nx = sx+dx;
                int ny = sy+dy;
                if (getpx(img, nx, ny) == WHITE || buf[nx+ny*img->w]) {
                    // skip adding point to fringe
                } else {
                    // push point to top of stack
                    point* new_point = (point*)malloc(sizeof(point));
                    new_point->x = nx;
                    new_point->y = ny;
                    new_point->next = stack;
                    new_point->parent = NULL;

                    stack = new_point;
                } 
            }
        }
        }
    }

    /*if (getpx(img, x, y) == WHITE || buf[x+y*img->w]) {
        return (shape){NULL, NULL, NULL};
    } else {
        buf[x+y*img->w] = 1;

        shape e  = floodfill_shape(img, ps, x+1, y,   buf);
        shape ne = floodfill_shape(img, ps, x+1, y+1, buf);
        shape n  = floodfill_shape(img, ps, x,   y+1, buf);
        shape nw = floodfill_shape(img, ps, x-1, y+1, buf);
        shape w  = floodfill_shape(img, ps, x-1, y,   buf);
        shape sw = floodfill_shape(img, ps, x-1, y-1, buf);
        shape s  = floodfill_shape(img, ps, x,   y-1, buf);
        shape se = floodfill_shape(img, ps, x+1, y-1, buf);

        point *p = alloc_point(ps);
        p->x = x;
        p->y = y;
        p->next = NULL;
        p->parent = NULL;

        shape o = (shape){p, p, NULL};
        if (e.first_point != NULL) {
            o.last_point->next = e.first_point;
            o.last_point = e.last_point;
        }
        if (ne.first_point != NULL) {
            o.last_point->next = ne.first_point;
            o.last_point = ne.last_point;
        }
        if (n.first_point != NULL) {
            o.last_point->next = n.first_point;
            o.last_point = n.last_point;
        }
        if (nw.first_point != NULL) {
            o.last_point->next = nw.first_point;
            o.last_point = nw.last_point;
        }
        if (w.first_point != NULL) {
            o.last_point->next = w.first_point;
            o.last_point = w.last_point;
        }
        if (sw.first_point != NULL) {
            o.last_point->next = sw.first_point;
            o.last_point = sw.last_point;
        }
        if (s.first_point != NULL) {
            o.last_point->next = s.first_point;
            o.last_point = s.last_point;
        }
        if (se.first_point != NULL) {
            o.last_point->next = se.first_point;
            o.last_point = se.last_point;
        }

        return o;
    }*/

    shape out = {first_explored, explored, NULL};

    return out;
}

shape* create_shapes(image* img, storage* ps) {
    char* added_buffer = (char*)calloc(img->w*img->h, sizeof(char));
    shape* first_shape = NULL;
    shape* last_shape = NULL;
    int num_shapes = 0;
    for (int y=0; y<img->h; y++) {
        for (int x=0; x<img->w; x++) {
            if (getpx(img, x, y) != WHITE && !(added_buffer[x+y*img->w])) {
                shape* alloced_shape = alloc_shape(ps);
                *alloced_shape = floodfill_shape(img, ps, x, y, added_buffer);

                if (first_shape == NULL) {
                    first_shape = alloced_shape;
                    last_shape = alloced_shape;
                } else if (last_shape != NULL) {
                    last_shape->next_shape = alloced_shape;
                    last_shape = alloced_shape;
                }

                num_shapes++;
            }
        }
    }

    free(added_buffer);

    return first_shape;
}

void populate_buf(image* img, shape* s, char* buf) {
    point* p = s->first_point;

    while (p != NULL) {
        buf[p->x+p->y*img->w] = 1;
        p = p->next;
    }
}

bool expand_frontier(image* img, storage* ps, shape* prev_frontier, shape* next_frontier, char* buf) {
    point* p = prev_frontier->first_point;
    point* n = NULL;

    bool found = false;

    size_t starting_points_index = ps->points_index;

    while (p != NULL) {
        for (int dy=-1; dy<2; dy++) {
        for (int dx=-1; dx<2; dx++) {
            if (dy != 0 || dx != 0) {
                int nx = p->x+dx;
                int ny = p->y+dy;
                if ((0<=nx && nx<img->w && 0<=ny && ny<img->h) // in bounds
                        && !buf[nx+ny*img->w]) {               // not searched yet
                    buf[nx+ny*img->w] = 1;
                    if (getpx(img, nx, ny) != WHITE) {
                        // found a new shape!
                        ps->points_index = starting_points_index;
                        n = alloc_point(ps);
                        n->x = nx;
                        n->y = ny;
                        n->next = NULL;
                        n->parent = p;
                        found = true;
                        goto __expand_frontier_fullbreak;
                    } else {
                        // need to search more
                        point* f = alloc_point(ps);
                        f->x = nx;
                        f->y = ny;
                        f->next = n;
                        f->parent = p;
                        n = f;
                    }
                }
            }
        }}

        p = p->next;
    }
__expand_frontier_fullbreak:
    p = NULL;
    point* last_n = n;
    while (last_n->next != NULL) {
        last_n = last_n->next;
    }

    next_frontier->first_point = n;
    next_frontier->last_point = last_n;

    return found;
}

void color_from_frontier(image* img, point* frontier_point) {
    point* p = frontier_point->parent;

    while (p->parent != NULL) { // if everything else is right,
                                // a frontier point should come in a chain of at least 3
                                // (f point (B) -> point to color (W) -> point in shape (B) -> NULL)
        img->buf[p->x+p->y*img->w] = RED;
        p = p->parent;
    }
}

int main(int argc, char** argv) {
    if (argc < 3) {
        printf("Error: first argument must be filename to load, second argument filename to save to.\n");
        return 1;
    }

    char* fname = argv[1];
    FILE* fp = fopen(fname, "r");

    if (fp == NULL) {
        printf("Error opening file \"%s\"\n", fname);
        return 1;
    }

    int w, h;
    w = 0;
    h = 0;
    fscanf(fp, "%d %d\n", &w, &h);

    if (w==0 || h==0) {
        printf("Error: invalid width/height specified\n");
        return 1;
    }

    char* buf = (char*)malloc(sizeof(char)*w*h+1);
    fgets(buf, w*h+1, fp);
    fclose(fp);

    image img = (image){w, h, buf};

    int nshapes = 0;
    storage* ps = create_storage(w, h);

    while (nshapes != 1) {
        // main loop, do processing step until one shape left
        ps->points_index = 0;
        ps->shapes_index = 0;

        shape* head = create_shapes(&img, ps);
        nshapes = 0;
        shape* pt = head;
        while (pt != NULL) {
            pt = pt->next_shape;
            nshapes++;
        }
        if (nshapes % 1024 == 0) {
            printf("shapes left: %d\n", nshapes);
        }
        if (nshapes == 1) {
            goto __main_task_complete;
        }


        shape* frontier = alloc_shape(ps);
        // making a copy so we can safely free later
        point* p = head->first_point;
        point* ffp = NULL;
        point* flp = NULL;
        while (p != NULL) {
            if (ffp == NULL) {
                ffp = alloc_point(ps);
                ffp->x = p->x;
                ffp->y = p->y;
                ffp->next = NULL;
                ffp->parent = NULL;
                flp = ffp;
            } else {
                point* fnp = alloc_point(ps);
                fnp->x = p->x;
                fnp->y = p->y;
                fnp->next = NULL;
                fnp->parent = NULL;

                flp->next = fnp;
                flp = fnp;
            }

            p = p->next;
        }
        frontier->first_point = ffp;
        frontier->last_point = flp;
        frontier->next_shape = NULL;

        char* visited_buf = (char*)calloc(img.w*img.h+1, sizeof(char));
        populate_buf(&img, frontier, visited_buf);

        shape* new_frontier = alloc_shape(ps);
        new_frontier->first_point = NULL;
        new_frontier->last_point = NULL;
        new_frontier->next_shape = NULL;

        while (!expand_frontier(&img, ps, frontier, new_frontier, visited_buf)) {
            frontier->first_point = new_frontier->first_point;
            frontier->last_point = new_frontier->last_point;
            new_frontier->next_shape = frontier;
        }

        free(visited_buf);
        color_from_frontier(&img, new_frontier->first_point);
__main_task_complete:
        img = img;
    }

    free_storage(ps);

    char* outfname = argv[2];
    fp = fopen(outfname, "w");

    if (fp == NULL) {
        printf("Error opening file \"%s\"\n", outfname);
        return 1;
    }

    fprintf(fp, "%d %d\n", img.w, img.h);
    fprintf(fp, "%s", img.buf);

    free(img.buf);

    fclose(fp);

    return 0;
}

Getestet auf: Arch Linux, GCC 9.1.0, -O3

Dieser Code übernimmt die Eingabe / Ausgabe in einer benutzerdefinierten Datei, die ich "cppm" nenne (da es sich um eine komprimierte Version des klassischen PPM-Formats handelt). Ein Python-Skript zum Konvertieren in / aus es ist unten:

from PIL import Image

BLACK='B'
WHITE='W'
RED  ='R'


def image_to_cppm(infname, outfname):
    outfile = open(outfname, 'w')
    im = Image.open(infname)

    w, h = im.width, im.height
    outfile.write(f"{w} {h}\n")
    for y in range(h):
        for x in range(w):
            r, g, b, *_ = im.getpixel((x, y))
            if r==0 and g==0 and b==0:
                outfile.write(BLACK)
            elif g==0 and b==0:
                outfile.write(RED)
            else:
                outfile.write(WHITE)
    outfile.write("\n")
    outfile.close()
    im.close()

def cppm_to_image(infname, outfname):
    infile = open(infname, 'r')

    w, h = infile.readline().split(" ")
    w, h = int(w), int(h)

    im = Image.new('RGB', (w, h), color=(255, 255, 255))

    for y in range(h):
        for x in range(w):
            c = infile.read(1)
            if c==BLACK:
                im.putpixel((x,y), (0, 0, 0))
            elif c==RED:
                im.putpixel((x,y), (255, 0, 0))

    infile.close()
    im.save(outfname)
    im.close()


if __name__ == "__main__":
    import sys
    if len(sys.argv) < 3:
        print("Error: must provide 2 files to convert, first is from, second is to")

    infname = sys.argv[1]
    outfname = sys.argv[2]

    if not infname.endswith("cppm") and outfname.endswith("cppm"):
        image_to_cppm(infname, outfname)
    elif infname.endswith("cppm") and not outfname.endswith("cppm"):
        cppm_to_image(infname, outfname)
    else:
        print("didn't do anything, exactly one file must end with .cppm")

Algorithmus Erklärung

Wie dieser Algorithmus funktioniert, beginnt er damit, alle verbundenen Formen im Bild zu finden, einschließlich roter Pixel. Dann nimmt es das erste und erweitert seine Grenze um jeweils ein Pixel, bis es auf eine andere Form stößt. Anschließend werden alle Pixel von der Berührung bis zur ursprünglichen Form eingefärbt (unter Verwendung der verknüpften Liste, die auf dem Weg erstellt wurde, um den Überblick zu behalten). Abschließend wird der Vorgang wiederholt, wobei alle neu erstellten Formen gefunden werden, bis nur noch eine Form übrig ist.

Bildergalerie

Testfall 1, 183 Pixel

Testfall 1

Testfall 2, 140 Pixel

Testfall 2

Testfall 3, 244 Pixel

Testfall 3

Testfall 4, 42 Pixel

Testfall 4

Testfall 5, 622 Pixel

Testfall 5

Testfall 6, 1 Pixel

Testfall 6

Testfall 7, 104 Pixel

Testfall 7

Testfall 8, 2286 Pixel

Testfall 8

Testfall 9, 22 Pixel

Testfall 9

Testfall 10, 31581 Pixel

Testfall 10

Testfall 11, 21421 Pixel

Testfall 11

Testfall 12, 5465 Pixel

Testfall 12

Testfall 13, 4679 Pixel

Testfall 13

Testfall 14, 7362 Pixel

Testfall 14

Blau
quelle
2
Gute Arbeit! Scheint sehr effizient zu sein, obwohl ich mir ein paar Formen mit etwas optimaleren Lösungen vorstellen kann: Testfall 3 (4 Punkte in einem Quadrat), zum Beispiel, ich bin (manuell) auf 175 (ein rotes X) gekommen, nicht sicher, wie Das würde ich per Algorithmus erzwingen.
BradC
6

Python, 2,62 * 10 ^ 40

Dieser Algorithmus füllt einfach die Ebene ausgehend von den schwarzen Teilen des Bildes aus (BFS), wobei wir für jedes neue Pixel aufzeichnen, von welchem ​​schwarzen Teil es geflutet wurde. Sobald wir zwei benachbarte Pixel mit unterschiedlichen schwarzen Teilen als Vorfahren haben, verbinden wir diese beiden schwarzen Teile im Grunde genommen, indem wir sie durch die Vorfahren der beiden Nachbarn verbinden, die wir gerade gefunden haben. Theoretisch könnte dies in implementiert werden O(#pixels), aber um die Codemenge auf einem akzeptablen Niveau zu halten, ist diese Implementierung etwas schlechter.

Ausgabe

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

import numpy as np
from scipy import ndimage
import imageio
from collections import deque

# path to your image
for k in range(1, 15):
    fname=str(k).zfill(2) +'.png'
    print("processing ", fname)

    # load image
    img = imageio.imread("./images/"+fname, pilmode="RGB")
    print(img.shape)

    # determine non_white part
    white = np.logical_and(np.logical_and(img[:,:,0] == 255, img[:,:,1] == 255), img[:,:,2] == 255)
    non_white = np.logical_not(white)

    # find connected components of non-white part
    neighbourhood = np.ones((3,3))
    labeled, nr_objects = ndimage.label(non_white, neighbourhood)

    # print result
    print("number of separate objects is {}".format(nr_objects))

    # start flood filling algorithm
    ind = np.nonzero(labeled)
    front = deque(zip(ind[0],ind[1]))

    membership = np.copy(labeled)
    is_merge_point = np.zeros_like(labeled) > 0
    parent = np.zeros((2,) + labeled.shape) #find ancestor of each pixel
    is_seed = labeled > 0
    size_i, size_j = labeled.shape
    # flood from every seed
    while front: #while we have unexplored pixels
        point = front.popleft()
        # check neighbours:
        for (di,dj) in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:
            current = membership[point[0], point[1]]
            new_i, new_j = point[0]+di, point[1]+dj
            if 0 <= new_i < size_i and 0 <= new_j < size_j:
                value = membership[new_i, new_j]
                if value == 0:
                    membership[new_i, new_j] = current
                    front.append((new_i, new_j))
                    parent[:, new_i, new_j] = point
                elif value != current: #MERGE!
                    is_merge_point[point[0], point[1]] = True
                    is_merge_point[new_i, new_j] = True
                    membership[np.logical_or(membership == value, membership == current)] = min(value, current)

    # trace back from every merger
    ind = np.nonzero(is_merge_point)
    merge_points = deque(zip(ind[0].astype(np.int),ind[1].astype(np.int)))
    for point in merge_points:
        next_p = point
        while not is_seed[next_p[0], next_p[1]]:
            is_merge_point[next_p[0], next_p[1]] = True
            next_p = parent[:, next_p[0], next_p[1]].astype(np.int)

    # add red points:
    img_backup = np.copy(img)
    img[:,:,0][is_merge_point] = 255 * img_backup[:,:,0]
    img[:,:,1][is_merge_point] = 0   * img_backup[:,:,1]
    img[:,:,2][is_merge_point] = 0   * img_backup[:,:,2]

    #compute number of new points
    n_red_points = (img[:,:,0] != img[:,:,1]).sum()
    print("#red points:", n_red_points)

    # plot: each component should have separate color
    imageio.imwrite("./out_images/"+fname, np.array(img))

Ergebnis

(1+183)*(1+142)*(1+244)*(1+42)*(1+1382)*(1+2)*(1+104)*(1+7936)*(1+26)*(1+38562)*(1+42956)*(1+6939)*(1+8882)*(1+9916)
= 26208700066468930789809050445560539404000
= 2.62 * 10^40
fehlerhaft
quelle
- Ich glaube, das ist optimal. Gut gemacht. - Okay, das ist nicht optimal. Ich verstehe nicht warum nicht.
wizzwizz4
@ wizzwizz4 Schau dir den einfachen Fall der vier Ecken eines Quadrats an: Die optimale Lösung wäre ein X. Obwohl mein Algorithmus diese Lösung theoretisch finden könnte, ist dies sehr unwahrscheinlich. Es ist viel wahrscheinlicher, dass es eine Lösung mit drei Pfaden findet, die jeweils zwei Punkte verbinden.
Fehler
@ wizzwizz4 Ja, wenn Sie das Wikipedia-Textbeispiel vergrößern, werden Sie Tonnen kleiner Orte sehen, an denen ein anderer Verbindungspfad ein oder zwei rote Pixel gespeichert hätte. sie werden addieren.
BradC
Aber das scheint wie Seifenblasen auf Pflöcken, was eine legitime Lösung für das Steiner-Baum-Problem ist .
wizzwizz4
1
@ wizzwizz4 Der Unterschied muss also sein, dass wir keine Punkte verbinden , wir verbinden Punktmengen , also müssen wir nicht entscheiden, welche Punkte in jeder Menge optimal verbunden werden sollen. Zoomen Sie erneut in das Textbeispiel. Die Verbesserungen, die Sie sehen, hängen hauptsächlich damit zusammen, welche Teile jeder Form verbunden sind.
BradC
5

Python 3: 1,7 x 10 ^ 42 1,5 x 10 ^ 41

Mit Pillow, numpyund scipy.

Es wird davon ausgegangen, dass imagessich die Bilder in einem Ordner befinden, der sich im selben Verzeichnis wie das Skript befindet.

Haftungsausschluss : Die Verarbeitung aller Bilder dauert sehr lange.

Code

import sys
import os

from PIL import Image
import numpy as np
import scipy.ndimage


def obtain_groups(image, threshold, structuring_el):
    """
    Obtain isles of unconnected pixels via a threshold on the R channel
    """
    image_logical = (image[:, :, 1] < threshold).astype(np.int)
    return scipy.ndimage.measurements.label(image_logical, structure=structuring_el)


def swap_colors(image, original_color, new_color):
    """
    Swap all the pixels of a specific color by another color 
    """
    r1, g1, b1 = original_color  # RGB value to be replaced
    r2, g2, b2 = new_color  # New RGB value
    red, green, blue = image[:, :, 0], image[:, :, 1], image[:, :, 2]
    mask = (red == r1) & (green == g1) & (blue == b1)
    image[:, :, :3][mask] = [r2, g2, b2]
    return image


def main(image_path=None):
    images = os.listdir("images")
    f = open("results.txt", "w")

    if image_path is not None:
        images = [image_path]

    for image_name in images:
        im = Image.open("images/"+image_name).convert("RGBA")
        image = np.array(im)

        image = swap_colors(image, (255, 255, 255), (255, 0, 0))

        # create structuring element to determine unconnected groups of pixels in image
        s = scipy.ndimage.morphology.generate_binary_structure(2, 2)

        for i in np.ndindex(image.shape[:2]):
            # skip black pixels
            if sum(image[i[0], i[1]]) == 255:
                continue
            image[i[0], i[1]] = [255, 255, 255, 255]
            # label the different groups, considering diagonal connections as valid
            groups, num_groups = obtain_groups(image, 255, s)
            if num_groups != 1:
                image[i[0], i[1]] = [255, 0, 0, 255]
            # Show percentage
            print((i[1] + i[0]*im.size[0])/(im.size[0]*im.size[1]))

        # Number of red pixels
        red_p = 0
        for i in np.ndindex(image.shape[:2]):
            j = (im.size[1] - i[0] - 1, im.size[0] - i[1] - 1)
            # skip black and white pixels
            if sum(image[j[0], j[1]]) == 255 or sum(image[j[0], j[1]]) == 255*4:
                continue
            image[j[0], j[1]] = [255, 255, 255, 255]
            # label the different groups, considering diagonal connections as valid
            groups, num_groups = obtain_groups(image, 255, s)
            if num_groups != 1:
                image[j[0], j[1]] = [255, 0, 0, 255]
            # Show percentage
            print((j[1] + j[0]*im.size[0])/(im.size[0]*im.size[1]))
            red_p += (sum(image[j[0], j[1]]) == 255*2)

        print(red_p)
        f.write("r_"+image_name+": "+str(red_p)+"\n")

        im = Image.fromarray(image)
        im.show()
        im.save("r_"+image_name)
    f.close()


if __name__ == "__main__":
    if len(sys.argv) == 2:
        main(sys.argv[1])
    else:
        main()

Erläuterung

Triviale Lösung. Wir beginnen damit, die Farbe aller weißen Pixel in einem Bild in Rot zu ändern. Auf diese Weise wird sichergestellt, dass alle Elemente (jede Insel schwarzer Pixel) verbunden sind.

Dann iterieren wir über alle Pixel im Bild, beginnend in der linken oberen Ecke und nach rechts und unten bewegend. Für jedes rote Pixel ändern wir seine Farbe in Weiß. Wenn es nach diesem Farbwechsel immer noch nur ein Element gibt (ein Element ist jetzt eine Insel aus schwarzen und roten Pixeln), lassen wir das Pixel weiß und fahren mit dem nächsten Pixel fort. Wenn jedoch nach dem Farbwechsel von Rot zu Weiß die Anzahl der Elemente größer als eins ist, lassen wir das Pixel rot und fahren mit dem nächsten Pixel fort.

Aktualisieren

Wie zu sehen (und zu erwarten) ist, weisen die Verbindungen, die nur mit dieser Methode erhalten werden, ein regelmäßiges Muster auf, und in einigen Fällen, wie in den Bildern 6 und 11, gibt es unnötige rote Pixel.

Diese zusätzlichen roten Pixel können leicht entfernt werden, indem Sie das Bild erneut iterieren und dieselben Vorgänge wie oben beschrieben ausführen, jedoch von der rechten unteren Ecke zur linken oberen Ecke. Dieser zweite Durchgang ist viel schneller, da die Anzahl der roten Pixel überprüft werden muss.

Ergebnisse

Die Bilder, die nach dem zweiten Durchgang geändert wurden, werden zweimal aufgelistet, um die Unterschiede anzuzeigen.

18825

Anzahl der roten Pixel: 18825

334

Anzahl der roten Pixel: 334

1352

Anzahl der roten Pixel: 1352

20214

Anzahl der roten Pixel: 20214

Bildbeschreibung hier eingeben

Anzahl der roten Pixel: 47268

63 Bildbeschreibung hier eingeben

Anzahl der roten Pixel: 63 27

17889

Anzahl der roten Pixel: 17889

259

Anzahl der roten Pixel: 259

6746

Anzahl der roten Pixel: 6746

586

Anzahl der roten Pixel: 586

9 Bildbeschreibung hier eingeben

Anzahl der roten Pixel: 9 1

126

Anzahl der roten Pixel: 126

212

Anzahl der roten Pixel: 212

683

Anzahl der roten Pixel: 683

Punktzahlberechnung:

(1 + 6746) * (1 + 126) * (1 + 259) * (1 + 17889) * (1 + 334) * (1 + 586) * (1 + 18825) * (1 + 9) * (1 +683) * (1 + 1352) * (1 + 20214) * (1 + 212) * (1 + 63) * (1 + 47268) = 1778700054505858720992088713763655500800000 ~ 1,7x10 ^ 42

Die Berechnung der Punktzahl nach dem Hinzufügen des zweiten Durchgangs wurde aktualisiert:

(1+ 18825) * (1+ 1352) * (1+ 20214) * (1+ 47268) * (1+ 27) * (1+ 17889) * (1+ 6746) * (1+ 586) * (1 + 1) * (1+ 126) * (1+ 212) * (1+ 334) * (1 + 259) * (1 + 683) = 155636254769262638086807762454319856320000 ~ 1,5x10 ^ 41

Ioannes
quelle
Gute Arbeit. Es sieht so aus, als müssten wir diesen in wissenschaftlicher Notation bewerten: 1.7x10 ^ 42
BradC