_           _                 
 | |_ ___  __| |____  ___ _   _ 
 | __/ _ \/ _` |_  / / _ \ | | |
 | ||  __/ (_| |/ / |  __/ |_| |
  \__\___|\__,_/___(_)___|\__,_|

Skeleton of binary image in C

Test PGM image:

• q_small.pgm

Input image (provided by David Adesoye):

Output image:

Current code (work in progress):

//
// skeleton.c - Written by Ted Burke 21-May-2025
//
// To compile:
//   gcc -g skeleton.c -o skeleton
// 
// To run:
//   ./skeleton q_small.pgm
//

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

void write_img(const char* filename, unsigned char* p, int w, int h);
void snap();
void dilate();
int erode();

int w, h;
unsigned char *p, *q, *temp;

int main(int argc, char** argv)
{
    FILE *f = NULL;
    int x, y, n;

    if (argc < 2) fprintf(stderr, "Please supply PGM image filename, e.g. ./skeleton image.pgm\n");

    // Load specified PGM image file into pixel buffer
    fprintf(stderr, "Opening file %s\n", argv[1]);
    f = fopen(argv[1], "r");
    char buf[256];
    fscanf(f, "%s\n", buf);
    fscanf(f, "%d %d\n", &w, &h);
    fscanf(f, "%s\n", buf);
    p = malloc(w*h); // buffer to store current version of image
    q = malloc(w*h); // used as destination buffer for image operations
    fread(p, 1, w*h, f);
    fclose(f);

    // Print some debugging info
    fprintf(stderr, "w%d h%d\n", w, h);

    snap(); // original image

    // invert image
    for (y=0 ; y<h ; ++y) for (x=0 ; x<w ; ++x) p[y*w+x] = p[y*w+x] > 127 ? 0 : 255;
    snap();

    // dilate glyph
    for (n=0 ; n<5 ; ++n) dilate();
    snap();

    // erode foreground
    for (n=0 ; n<1000 && erode() ; ++n) fprintf(stderr, "%d\n", n);
    snap();

    // free allocated memory
    free(p);
    free(q);
    return 0;
}

void dilate()
{
    int x, y, dx, dy;

    for (y=0 ; y<h ; ++y) for (x=0 ; x<w ; ++x) q[y*w+x] = 0;
    for (y=0 ; y<h ; ++y) for (x=0 ; x<w ; ++x) if (p[y*w+x] > 0)
    {
        for (dx=-1 ; dx<=1 ; ++dx) for (dy=-1 ; dy<=1 ; ++dy)
            if (x+dx >= 0 && x+dx <= w-1 && y+dy >= 0 && y+dy <= h-1)
                q[(y+dy)*w+(x+dx)] = 255;
    }

    temp = p; p = q; q = temp; // swap buffers
}

int erode()
{
    int x, y, connections, neighbours;

    int eroded = 0;

    for (y=0 ; y<h ; ++y) for (x=0 ; x<w ; ++x) q[y*w+x] = p[y*w+x];

    for (y=0 ; y<h ; ++y) for (x=0 ; x<w ; ++x)
    {
        if (x==0 || x==w-1 || y==0 || y==h-1) q[y*w+x] = 0;
        if (q[y*w+x] == 0) continue;

        connections = 0;
        if (q[(y-1)*w+(x-1)]==0 && q[(y-1)*w+(x)]>0) connections++;
        if (q[(y-1)*w+(x)]==0 && q[(y-1)*w+(x+1)]>0) connections++;
        if (q[(y-1)*w+(x+1)]==0 && q[(y)*w+(x+1)]>0) connections++;
        if (q[(y)*w+(x+1)]==0 && q[(y+1)*w+(x+1)]>0) connections++;
        if (q[(y+1)*w+(x+1)]==0 && q[(y+1)*w+(x)]>0) connections++;
        if (q[(y+1)*w+(x)]==0 && q[(y+1)*w+(x-1)]>0) connections++;
        if (q[(y+1)*w+(x-1)]==0 && q[(y)*w+(x-1)]>0) connections++;
        if (q[(y)*w+(x-1)]==0 && q[(y-1)*w+(x-1)]>0) connections++;
        if (connections > 1) continue;

        neighbours = 0;
        if (q[(y-1)*w+(x-1)]>0) neighbours++;
        if (q[(y-1)*w+(x)]>0) neighbours++;
        if (q[(y-1)*w+(x+1)]>0) neighbours++;
        if (q[(y)*w+(x+1)]>0) neighbours++;
        if (q[(y+1)*w+(x+1)]>0) neighbours++;
        if (q[(y+1)*w+(x)]>0) neighbours++;
        if (q[(y+1)*w+(x-1)]>0) neighbours++;
        if (q[(y)*w+(x-1)]>0) neighbours++;

        if (p[(y-1)*w+(x)]==0 || p[(y)*w+(x+1)]==0 || p[(y+1)*w+(x)]==0 || p[(y)*w+(x-1)]==0)
        {
            q[y*w+x] = 0;

            if (neighbours > 1) eroded++;
        }
    }

    temp = p; p = q; q = temp; // swap buffers

    return eroded;
}

// Record a snapshot image
void snap()
{
    static int n = 0;
    char filename[256];
    sprintf(filename, "snap_%04d.pgm", n++);
    fprintf(stderr, "Writing file %s...", filename);
    write_img(filename, p, w, h);
    fprintf(stderr, "Done\n");
}

// Write image to file
void write_img(const char* filename, unsigned char* p, int w, int h)
{
    FILE *f = fopen(filename, "w");
    fprintf(f, "P5\n%d %d\n255\n", w, h);
    fwrite(p, 1, w*h, f);
    fclose(f);
}