Преодолеть разрыв

14

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

Детали

  • Путь - это набор связанных пикселей (8-соседняя связь). Черные пиксели могут использоваться как часть контуров. Цель состоит в том, чтобы минимизировать набор красных пикселей при указанных выше условиях и вывести соответствующее изображение.

  • Вам не нужно находить оптимальное решение.

  • Тривиальное и в то же время худшее решение - просто покрасить все белые пиксели в красный.

  • Пример (пиксели увеличены для наглядности):

Детали

  • Для данного пиксельного изображения (в любом подходящем формате) вернуть другое изображение с точками, соединенными, как указано выше, а также целое число, указывающее, сколько было использовано красного пикселя.
  • Оценка является произведением (1 + количество красных пикселей) для каждого из 14 тестовых случаев.
  • Цель - набрать наименьшее количество очков.

Testcases

14 тестовых случаев показаны ниже. Программа Python для проверки связности выходов может быть найдена здесь.

Мета

Спасибо @Veskah, @Fatalize, @wizzwizz4 и @trichoplax за различные предложения.

flawr
источник
1
Хороший вызов; Мне нравятся те, у кого разные и креативные схемы подсчета очков. Я предполагаю, что программа должна работать с произвольным изображением, а не только с этими 14 конкретными примерами? Если да, можем ли мы предположить разумный максимальный размер, например, 512x512 для изображения Моны Лизы или 1024x1024?
BradC
Спасибо за ответ! Да, вы можете принять максимальный размер (также минимальный размер при необходимости), если все 14 примеров могут быть обработаны.
19
Как я могу конвертировать PNG в ASCII или JSON или что-то еще, легко разобрать?
19
Вы должны быть в состоянии вычислить свой собственный счет? Программа, которая пробует каждую возможную комбинацию белых пикселей, чтобы закрасить красным, и видит, какое подмножество имеет наименьшее количество красных пикселей, в то время как соединение всех черных пикселей будет иметь наилучшую возможную оценку, но это будет настолько медленно, что это займет больше времени, чем время жизни. Вселенной, чтобы на самом деле вычислить этот счет.
Лев Тененбаум
1
@ngn Открыть в GIMP, сохранить в формате netpbm.
wizzwizz4

Ответы:

7

С, оценка 2,397х10 ^ 38

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

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

Во всяком случае, вот код:

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

Проверено на: Arch Linux, GCC 9.1.0, -O3

Этот код принимает ввод / вывод в пользовательском файле, который я называю «cppm» (потому что он похож на сжатую версию классического формата PPM). Сценарий Python для преобразования в / из него приведен ниже:

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

Объяснение алгоритма

Этот алгоритм работает так, что он начинает с нахождения всех связанных фигур на изображении, включая красные пиксели. Затем он берет первый и расширяет свою границу по одному пикселю за раз, пока не встретит другую форму. Затем он окрашивает все пиксели от касания до исходной формы (используя связанный список, который он создал по пути отслеживания). Наконец, он повторяет процесс, находя все новые созданные фигуры, пока не останется только одна фигура.

Галерея

Тест-кейс 1, 183 пикселя

контрольный пример 1

Тест-кейс 2, 140 пикселей

контрольный пример 2

Тест-кейс 3, 244 пикселя

контрольный пример 3

Тест-кейс 4, 42 пикселя

контрольный пример 4

Тест-кейс 5, 622 пикселей

контрольный пример 5

Тестовый случай 6, 1 пиксель

контрольный пример 6

Тест-кейс 7, 104 пикселя

контрольный пример 7

Тест-кейс 8, 2286 пикселей

контрольный пример 8

Тест-кейс 9, 22 пикселя

контрольный пример 9

Тест-кейс 10, 31581 пикселей

контрольный пример 10

Тест-кейс 11, 21421 пикселей

контрольный пример 11

Testcase 12, 5465 пикселей

контрольный пример 12

Тест-кейс 13, 4679 пикселей

контрольный пример 13

Testcase 14, 7362 пикселей

контрольный пример 14

синий
источник
2
Хорошо сделано! Кажется очень эффективным, хотя я могу представить несколько фигур с чуть более оптимальными решениями: например, тестовый пример 3 (4 точки в квадрате), я (вручную) получил всего 175 (красный X), не знаю, как Я бы форсировал это с помощью алгоритма.
BradC
6

Python, 2.62 * 10 ^ 40

Этот алгоритм просто заполняет (BFS) плоскость, начиная с черных частей изображения, где для каждого нового пикселя мы записываем, из какой черной части оно было затоплено. Как только у нас есть два соседних пикселя с разными черными частями в качестве предков, мы в основном объединяем эти две черные части, соединяя их через предков двух соседей, которых мы только что нашли. Теоретически это может быть реализовано в O(#pixels), но чтобы сохранить объем кода на приемлемом уровне, эта реализация немного хуже.

Выход

введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь введите описание изображения здесь

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

Гол

(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
flawr
источник
- Это, я считаю, оптимально. Хорошо сделано. Хорошо, это не оптимально. Я не понимаю, почему нет.
wizzwizz4
@ wizzwizz4 Посмотрите на простой случай четырех углов квадрата: оптимальным решением будет X. Хотя теоретически мой алгоритм мог бы найти это решение, это очень маловероятно. Скорее всего, он найдет решение с тремя путями, каждый из которых соединяет две точки.
flawr
@ wizzwizz4 Да, увеличьте пример текста в Википедии, и вы увидите тонны маленьких мест, где другой путь соединения спас бы красный или два пикселя; они сложат.
BradC
Но это похоже на мыльные пузыри на колышках, что является законным решением проблемы дерева Штейнера .
wizzwizz4
1
@ wizzwizz4 Разница в том, что мы не соединяем точки , мы соединяем наборы точек, поэтому мы не должны решать, какие точки в каждом наборе соединять оптимальным образом. Снова увеличьте текстовый пример, улучшения, которые вы видите, в основном связаны с тем, какие части каждой фигуры связаны.
BradC
5

Python 3: 1.7x10 ^ 42 1.5x10 ^ 41

Использование Pillow, numpyи scipy.

Предполагается, что изображения находятся в imagesпапке, расположенной в том же каталоге, что и скрипт.

Отказ от ответственности : обработка всех изображений занимает много времени.

Код

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

объяснение

Простое решение. Мы начинаем с изменения цвета всех белых пикселей на изображении на красный. При этом гарантируется, что все элементы (любой остров чёрных пикселей) связаны.

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

Обновить

Как можно видеть (и ожидаемо), соединения, полученные только с использованием этого метода, показывают регулярную структуру, и в некоторых случаях, например на 6-м и 11-м изображениях, появляются ненужные красные пиксели.

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

Результаты

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

18825

Количество красных пикселей: 18825

334

Количество красных пикселей: 334

1352

Количество красных пикселей: 1352

20214

Количество красных пикселей: 20214

введите описание изображения здесь

Количество красных пикселей: 47268

63 введите описание изображения здесь

Количество красных пикселей: 63 27

17889

Количество красных пикселей: 17889

259

Количество красных пикселей: 259

6746

Количество красных пикселей: 6746

586

Количество красных пикселей: 586

9 введите описание изображения здесь

Количество красных пикселей: 9 1

126

Количество красных пикселей: 126

212

Количество красных пикселей: 212

683

Количество красных пикселей: 683

Расчет баллов:

(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

Обновлен расчет счета после добавления второго прохода:

(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
источник
Хорошо сделано. Похоже, нам, возможно, понадобится забить это в научной записи: 1.7x10 ^ 42
BradC