Binary Image Processing Library

By Malcolm Mclean Homepage

The binary image processing library is a simple lightweight C library for processing binary images.

It's currently in a very initial stage of development. The idea is to collect all important algorithms for dealing with binary images in one place, and make them freely available as clean C source which compiles portably under ANSI C.

All the binary images are passed in as unsigned char arrays, with unset pixels represented by 0 and set pixels represented by 1. Its the user's responsibility to ensure that the images are valid. If a pixel is some value other than 1 or zero it might be treated as set, as unset, or something unexpected might happen. There's no “image” structure. Inventing an image structure would reduce the number of parameters to each function, but at a cost of making the library more difficult to integrate with other code. The goal is that most functions can be snipped and pasted, so you don't have to pull in the whole library just to use one or two functions.

The library is currently in five files, one for image processing functions as such, one for drawing routines, one for the distance transform, one for Canny edge detection, and one for halftoning. More files will be created as more functions are added.

See

  • binary drawing routines .
  • distance transform .
  • halftoning routines
  • DOS-style font routines
  • Canny edge detection
  • binary image rotation
  • Otsu thresholding
  • A* pathfinding
  • Source files

    binaryutils.c
    binaryutils.h

    distancetransform.c
    distancetransform.h
    drawbinary.c
    canny.c
    canny.h
    rotatebyshear.c
    rotatebyshear.h
    Otsuthreshold.c
    Otsuthreshold.h
    astar.h
    astar.c
    medialaxistransform.h
    medialaxistransform.c
    pcfont.c
    pcfont8x8.h
    pcfont8x19.h
    pcfontchars.h

    List of functions

  • invertbinary
  • copybinary
  • subbinary
  • boundingbox
  • simplearea
  • complexarea
  • perimeter
  • ends
  • labelconnected
  • eulernumber
  • getbiggestobject
  • morphclose
  • morphopen
  • dilate
  • erode
  • compressbinary
  • decompressbinary
  • Simple utilities

    These are quick functions which need to be in the library but are trival to write.

    invertbinary

    Inverts a binary image. In place.

    Fred inverted

    void invertbinary(unsigned char *binary, int width, int height)

    binary – the binary image.
    width – image width.
    height – image height.


    copybinary

    Copy a binary image.

    unsigned char *copybinary(unsigned char *binary, int width, int height)

    binary – the binary image.
    width – image width.
    height – image height.

    Returns: malloced copy of image, 0 on out of memory.


    subbinary

    Get a subimage from a binary image. If the sub image extends beyond the boundaries of the bianry image, it pads with zeros. So this function can also be used to add a border.

    unsigned char *subbinary(unsigned char *binary, int width, int height, int x, int y, int swidth, int sheight)

    binary – the binary image.
    width – image width.
    height – image height.
    x, y – sub image top left x, y co-ordinates.
    swidth, sheight – width and height of the sub image, in pixels.

    Returns: malloced sub image, 0 on out of memory.


    boundingbox

    Gets the bounding box of the set pixels.

    void boundingbox(unsigned char *binary, int width, int height, int *x, int *y, int *bbwidth, int *bbheight)

    binary - the binary image.
    width - image width.
    height - image height.
    x, y - return for bounding box top left co-ordiantes.
    bbwidth, bbheight - return for bounding box dimensions.


    simplearea

    Simple area simply counts the set pixels.

    int simplearea(unsigned char *binary, int width, int height)

    binary - the image.
    width - image width.
    height - image height.

    Returns: number of set pixels.


    complexarea

    Complex area tries to determine the real area of the underlying image covered by the set pixels. It use a 2x2 neighbourhood.
  • Patterns with zero set pixels (area = 0)
  • Patterns with one set pixel (area = 1/4)
  • Patterns with two adjacent set pixels (area = 1/2)
  • Patterns with two diagonal set pixels (area = 3/4)
  • Patterns with three set pixels (area = 7/8)
  • Patterns with all four set pixels (area = 1)
  • Each pixel is in four 2x2 neighbourhoods, so the area of a single set pixel is 1.

    double complexarea(unsigned char *binary, int width, int height)

    binary - the binary image.
    width – image width.
    height image height.

    Returns: image area using the above algorithm.

    Morphology

    Morphology collects functions which work on limited neighbourhoods, usually 3x3.

    perimeter

    The perimeter of a binary image is simply any set pixel which has an unset pixel as a neighbour. Pixels beyond the border are assumed to be unset.

    unsigned char *perimeter(unsigned char *binary, int width, int height)(

    binary - the binary image
    width - image width
    height - image height

    Returns: malloced array to image with perimeter pixels set.


    ends

    Ends are the end-points of lines, or any set pixel with exactly one neighbour.

    int ends(unsigned char *binary, int width, int height, int **xout, int *yout)

    binary - the binary image.
    width - image width.
    height - image height.
    xout - return for end x co-ordinates. yout - return for end y co-ordinates.
    Returns: number of end points found (-1 on out of memory).

    xout and yout are allocated with malloc().


    branchpoints

    Branchpoints are points where two lines meet. They can be detected by the fact that there are more than two “crossings” in the circle of neighbours around the pixel.

    int branchpoints(unsigned char *binary, int width, int height, int **xout, int *yout)

    binary - the binary image.
    width - image width.
    height - image height.
    xout - return for end x co-ordinates. yout - return for end y co-ordinates.
    Returns: number of branch points found (-1 on out of memory).

    xout and yout are allocated with malloc().


    Connected Component Labelling

    Connected component labelling is assigning a label to the “blobs” in the binary image.

    A binary image consists of several connected components. Labelling identifies those components and assigns an integer label to them. The background is labelled zero. We can have 4-connected or 8-connected components. Labellign connected components is a first step in high-order image processing algorithms.

    labelconnected

    Returns an array of labels. Label zero always represents the background. Nout returns the total number of labels, which go from 0 to *Nout -1.

    Results of labelling Fred. Each region is shown in a different colour.

    int *labelconnected(unsigned char *binary, int width, int height, int connex, int *Nout)

    binary - the binary image.
    width - image width.
    height - image height.
    connex - connectivity (4 or 8).
    Nout - return for number of connected components discovered (plus one for background)

    Returns: malloced width * height array of component indices.

    Algorithm

    The algorithm makes three passes over the image: one pass to record equivalences and assign temporary labels the second to replace each temporary label by the label of its equivalence class, and the third to make the labels into a series from 0 to N-1.

    Connectivity checks are carried out by checking the labels of pixels that are North-East, North, North-West and West of the current pixel (assuming 8-connectivity). 4-connectivity uses only North and West neighbors of the current pixel. The following conditions are checked to determine the value of the label to be assigned to the current pixel (8-connectivity is assumed)

    Conditions to check:

  • Get labels for the pixels to the West, North-West, North and North-East.
  • If all the labels are zero, assign the pixel a new label, and continue.
  • Assign the the pixel one of the non-zero labels
  • If any non-zero labels are not equal to the pixel label, assing both labels to the same equivalence group
  • The algorithm continues this way, and creates new region labels whenever necessary. The key to a fast algorithm, however, is how this merging is done. An array of “parents” is maintained. An ancestor, or the root of an equivalence group, is its own parent. To merge two equivalence groups, we find the ancestors, then set the high-valued ancestor to be the descendent of the lower-valued ancestor. To speed things up a bit, we also set the two labels to point directly to the new ancestor.


    eulernumber

    The Euler number is the number of objects in an image, minus the number of holes.

    int eulernumber(unsigned char *binary, int width, int height)

    binary - the binary image.
    width - image width.
    height - image height.

    Returns: the Euler number, or INT_MIN on out of memory.

    The Euler number is calculated using component labelling. The function then inverts the image and labels 4-connected components to count the holes. "Holes" which touch an edge are not counted as holes.


    getbiggestobject

    Get the biggest object in the image. Objects can be 8 or 4 connected.

    Images show the results of getting the 8-connected and 4-connected biggest objects in Fred.

    int getbiggestobject(unsigned char *binary, int width, int height, int connex)

    binary - the binary image (in / out)
    width - image width.
    height - image height
    connex connectivity - 4 or 8.

    Returns: 0 on success, -1 on fail (out of memory).


    Structuring elements

    Structuring elements are the binary image equivalent of filtering. There are two fundamental operations, erosion and dilation. They take a structuring element which is the equivalent of a filter kernel. The structuring element is moved so it centres over every pixel. Erosion means that if a pixel is set, and any pixel covered by the structuring element is unset, the pixel is cleared. Dilation means that if a pixel is unset, and any pixel covered by the structuring element is set, it is set.

    There's a huge amount of work done of structuring elements and the current functions are very preliminary, using the naïve algorithm.

    erode

    Perform the erosion operation. Specify the structuring element as a binary mask.

    Here's Fred eroded with the element [1 1 1]. Vertical lines disappear.

    int erode(unsigned char *binary, int width, int height, unsigned char *sel, int swidth, int sheight)

    binary - the binary image.
    width - image width.
    height - image height.
    sel - the structuring element.
    swidth - width of structuring element (should be odd).
    sheight - height of structuring element (should be odd).

    Returns: 0 on success, -1 on fail (out of memory).


    dilate

    Perform the dilation operation. Specify the structuring element as a binary mask.

    Here's Fred dilated with the structuring element [1 1 1]. Vertical lines get thicker.

    int dilate(unsigned char *binary, int width, int height, unsigned char *sel, int swidth, int sheight)

    binary - the binary image.
    width - image width.
    height -image height.
    sel - the structuring element
    swidth - structuring element width (should be odd).
    sheight - structuring element height (shold be odd).


    morphopen

    Performs morphological opening (erosion followed by dilation with the same structuring element).

    The result of morphological opening on Fred, with the structuring element [1 1 1]. int morphopen(unsigned char *binary, int width, int height, unsigned char *sel, int swidth, int sheight)

    binary - the binary image.
    width - image width.
    height - image height.
    sel - the structuring element
    swidth - structuring element width (should be odd).
    sheight - structuring element height (shold be odd).

    Returns: 0 on success, -1 on fail (out of memory).


    morphclose

    Performs morphological closing (dilation followed by erosion with the same structuring element).

    The result of morphological closing on Fred, with the structuring element [1 1 1]. Almost nothing happens, but some of the letters are fused.

    int morphclose(unsigned char *binary, int width, int height, unsigned char *sel, int swidth, int sheight)

    binary - the binary image.
    width - image width.
    height - image height.
    sel - the structuring element
    swidth - structuring element width (should be odd).
    sheight - structuring element height (shold be odd).

    Returns: 0 on success, -1 on fail (out of memory).

    Compression

    It's often necessary to compress a binary image, for instance if you need to store a large number in memory. The following routines won't won any prizes for the best compression ratio available, but they are fast and they take out the bulk of the memory.

    The compression routine returns a pointer to a malloced memory buffer. If saving the data to disk you will need to store the buffer length as well.

    compressbinary

    void *compressbinary(unsigned char *binary, int width, int height, int *clen)

    binary - the binary image.
    width - image width.
    height - image height.
    clen - return for length of compressed data.

    Returns: pointer to malloced buffer containg compressed data.


    decompressbinary

    Decompress a binary image from memory buffer. unsigned char *decompressbinary(unsigned char *comp, int *width, int *height)

    comp – the compressed memory buffer returned by compressbinary.
    width - return pointer for image width.
    height - return pointer for image height.

    Returns: malloced buffer to binary image data, 0 on out of memory.


    Algorithm

    width and height are stored as two 16-bit values at the beginning of the data.
    It then stores a byte to tell us whether the image starts with a 1 or a zero.
    From then on, we simply store run lengths in unsigned bytes. If a run of 1s or zeros is larger than 255, we simply put a run of zero between them. We don't need to store an end semaphore because we know that width * height pixels are stores.
     width (16 bits big endian)
     height (16 bit big endian)
     1 or zero – starting bit.
    { runlengths of alternating 1s and zeros, 1 byte per run };