Main Page

Fugenschnitzer Program Library 0.8 beta 2
Programmer's Manual

Fugenschnitzer—Seam Carving for everyone.
Copyright © 2008/9 David Eckardt
http://fugenschnitzer.sourceforge.net

Contents

Function Index

Image Data

Data Format

The image must be present as a data buffer/1D array. The elementary data type is comp_t. This is an unsigned 32 bit integer type. Each element correspond to an image pixel in RGB colour model with 8 bits per channel. For 1 byte = 8 bit, the lowest byte corresponds to the R channel, the second lowest to G and the third lowest to B.
Since the image elements have a width of 32 bits, they provide space for four channels @ 8 bits. The remaining channel is ignored by seam computation, however, its is processed when resizing the image.

Memory Allocation

If the image is only shrinked, the invoking program does not need to allocate further memory than is neccessary to hold the image in the beginning. If, on the other hand, the image should be enlarged, the invoking program has to allocate additional memory before it can retrieve the image back. The function sc_prepare tells through the parameters width and height how much memory the image will occupy at most. After calling sc_prepare the maximal image size is
width * height * sizeof(comp_t).

Functions

Basic Functions

The functions for basic image resizing are following listed in the order of invocation.

void sc_init(void)
Initializes everything. This function must me called exactly once, that is, before any other function call, and never again.
bool sc_load(
const comp_t *image,
long int *width, long int *height,
int zoom
)
Loads the image.
int sc_prepare(
const bool vertical,
const long int extend,
const bool interpol,
long int *width, long int *height,
long int *pwidth, long int *pheight
)
Prepares for seams computation and image resizing. This especially determines the resizing direction.
bool sc_seam(long int last)
Computes last seams.
long int sc_carve(
long int nom,
long int *width, long int *height,
long int *pwidth, long int *pheight
)
Resizes the image so that its measures differ from the original measures by nom pixels. To make the image smaller than the original, nom must be negative and positive to make it larger. The image is resized at most by as many pixels as seams have been computed at this time. If the image should get larger than the original, that is, nom > 0, it will be enlarged at most by as many pixels as have been given before to sc_prepare through the extend parameter.
bool sc_fix(
const bool restore,
long int *width, long int *height,
long int *pwidth, long int *pheight
)
Fixes the image. That means it is fixed to its actual state, discarding the computed seams and releasing the image resizing direction
void sc_eject(comp_t *image)
Outputs the image.
void sc_close(void)
Closes everything.

Advanced Functions

Preview Image

It is possible to retrieve a downscaled preview image of the image currently being processed. This is intended for the case when an image should be displayed which measures exceed the display measures.
To generate the preview image, when calling sc_load a scaling factor z > 1 must be given through the zoom parameter. sc_preview then outputs the preview image. The preview image represents the image being processed in its actual state, with width and height divided by z.
The same rules as for the memory of the original image apply for the memory of the preview image. If the image is enlarged to a size greater than the original size, additional memory must be allocated for the preview image. Through the pwidth and pheight parameters sc_prepare tells how much memory must be allocated for the preview image, in analogy to width und height. sc_carve and sc_fix tell the actual preview image size through these parameters.

void sc_preview(comp_t *image)
Outputs the preview image.

Subsequent Image Extension

The maximum image size which is given through the extend parameter to sc_prepare can subsequently extended while processing the image. This can be done by calling sc_extend. This function behaves the same like sc_prepare regarding its parameters and return value. After calling sc_extend, like sc_prepare, it may be neccessary to allocate additional image memory.

int sc_extend(
const long int extend,
long int *width, long int *height,
long int *pwidth, long int *pheight
)
Subsequently extends the image so that its size can exceed its original size at most by extend pixels. See sc_prepare for parameter desctiptions.

Program Procedure

Requirements

First the image must be loaded. As mentioned, the data format is RGB with 8 bits/1 byte per channel and 32 bits/4 bytes per pixel. The lowest byte represents the R channel. If the image is present as a 1D array of bytes in RGBA or RGB32 format, it simply can be C casted to comp_t*. If you do so, please pay attention of the machine's byte order/endianness.
For the image measures, width and height, each one long int variable must be provided. In these variables the initial image size must be stored. Pointers to these variables are then given to the library functions.

Simple procedure: Loading, resizing, ejecting.

Supposed the image is present as 1D array of comp_t *image and its size is stored in the variables long int x (width) und long int y (height). We want to enlarge the image by 50 pixels in horizontal direction and interpolate the inserted pixels.

We are done! image now contains the resized image and x and y the new image measures. The image now can be saved to a file.

Interaction: Resizing several times

Between the sc_prepare and sc_fix calls we can call sc_seam, sc_carve and sc_eject several times as we like. sc_seam each time extends the range whithin sc_carve can perform resizing. This is a way to implement a user interaction facility which allows the user to arbitrary resize the image before he fixes it to a certain size.
sc_eject always outputs the image at its maximum size which is the original size plus, in the resizing direction, the number of pixels given to sc_prepare through the extend parameter. The spare pixels in each image line or row must be ignored by the invoking program and clipped when displaying the image.
Here the enhancements for the example above:

Multi-Threaded Processing And Parallelized Computation

Fugenschnitzer is designed for multi-threaded program flow and parallelized computation. Initialization and synchronization of the running threads must be done by the invoking program. The functions used for this feature are not thread safe on their own, that means they do not automatically prevent possible conflicts which can occur if reentrant functions are called arbitrary times, at any time and in any order. Instead, the invoking program needs to stay in dialog with the library functions. However, the effort for this is quite low and much lower and less liable to errors at all than a complete thread management system would be.

Progress Query And Seam Computation Cancellation

long int sc_seam_progress(void)
Queries the progress of a running seam computation.

Note: This function may be called at any time.

long int sc_seam_cancel(void)
Cancels a running seam computation after the current seam has been finished. sc_seam_progress tells the progress so far.

Note: This function may be called at any time.

Parallelized Seam Computation

The seam computation processes can be parallelized. Parallelization affects the computation of a single seam. One seam has to be computed and processed before computation of the next seam can begin. Seam computation parallelization takes place by segmenting independent operations in three stages:

  1. simultaneous differentiation
  2. accumulation of differentiated image lines while simultaneously differentiating the following ones
  3. simultaneously applying the computed seam to several image parts

Simultaneous Differentiation and Accumulation

To start accumulation while differentiation is still running, the image is divided into parts. Each part consists of a certain number of lines. The invoking program tells how many pixels should be at least contained in each part; the default value is 65536.
The control functions for the parallel running differentiation and accumulation processes are:

  1. sc_seam_paral_diff
  2. sc_seam_paral_accu
  3. sc_seam_paral_seam

Parallelized Differentiation

The differentiation process itself can also be parallelized by differentiating several image clips. Together with a simultaneously running accumulation process means this that every image part is divided into clips. Each of these clips is processed by a differentiation thread. The invoking program initially indicates the number of threads; Fugenschnitzer then divides the image width into the desired number of threads.

Procedure Scheme and Initialization/Termination

As mentioned above the parallelized seam computation takes place for one seam at a time (in contrast to sc_seam). The invoking program therefore must have a seam counting loop. Before starting and after finishing the computation sc_seam_paral_init or sc_seam_paral_close must be called, respectively. This leads to the following scheme:

  1. sc_seam_paral_init
  2. (seam computation counting loop)
  3. sc_seam_paral_close .

The single seam computation itself consists of two loops: A differentiation and an accumulation loop. These two loops run simultaneously; the accumulation loop must be synchronized depending on the differentiation loop.
Before these loops start sc_seam_paral_start is called. After they are finished sc_seam_paral_seam_init is called followed by sc_seam_paral_seam. Finally the processing of the seam is finished by calling sc_seam_paral_finish.
This leads to the following process of one single seam computation loop period:

  1. sc_seam_paral_start
  2. (differentiation loop, several differentiation threads) → synchronizing → (accumulation loop)
  3. sc_seam_paral_seam_init
  4. sc_seam_paral_seam (runs in multiple threads simultaneously)
  5. sc_seam_paral_finish

Starting Threads And Synchronization

As mentioned, the invoking program must perform the thread start and the appropriate synchronization of the differentiation and the accumulation loop. Since these loops run simultaneously, each of them must run in its own loop. The functionality requirements to the invoking program are:

  1. Start a thread,
  2. wait for one or more threads to finish,
  3. send an integer value message from one thread to another,
  4. wait for a message to arrive and propagate its content.

These functions can be implemented using the basic functions of a multi thread library like pthreads.

Functions

Here the parallelized seam computation functions in the order of invocation:

void sc_seam_paral_init(void)
Initiates seam computation.
int sc_seam_paral_start(
long int samples,
int threads
)
Starts the parallelized computation of a single seam.
void sc_seam_paral_diff(
const int part,
const int thread
)
Differentiation function for parallelized seam computation.
bool sc_seam_paral_accu(const int part)
Accumulation function of the parallelized seam computation.
void sc_seam_paral_seam_init(const int threads)
Initializes processing the current seam.
void sc_seam_paral_seam(const int thread)
Seam processing function.
long int sc_seam_paral_finish(void)
Finishes the parallelized computation of the current seam.
void sc_seam_paral_close(void)
Finihes the seam computation.

Code Example

compute_seams is the main function. diff_loop and accu_loop represent the differentiation and accumulation loop. Starting threads and waiting for them to finish is done by the start_thread and join_thread pseudo functions which use the thread_t pseudo data type. Such a functionality provides the pthreads library, for example. Differentiation and accumulation loop is done by the send_message and wait_for_message pseudo functions which perform a message queue task. The important thing is that sc_seam_paral_accu may only process an image part which has been processed by sc_seam_paral_diff before.

Library functions are marked up bold, variable identifiers variable-styled and pseudo functions/data types italic.

Parallelized Image Resizing

Procedure Scheme

The image resizing operation can also be parallelized. This is done according to the following scheme:

  1. Initialize parallelized resizing by calling sc_carve_paral_init. The invoking program here gives the number threads of instances it will create (or threads, resepctively, if each instance will run in its own thread).
  2. Perform resizing by calling sc_carve_paral. This function must be called threads times (threads as given to sc_carve_paral_init). The several instances of sc_carve_paral may run simultaneously.
  3. After all instances of sc_carve_paral are finished, finish the operation by calling sc_carve_paral_finish.

Progress Query

While sc_carve_paral is running—optionally in several instances simultaneously—, the invoking program may query the progress by calling sc_carve_paral_progress.

Functions

long int sc_carve_paral_init(
long int nom,
int threads
)
Initializes parallelized image reszing.
void sc_carve_paral(const int thread)
Parallelized image resizing function.
long int sc_carve_paral_finish(
long int *width, long int *height,
long int *pwidth, long int *pheight,
)
Finishes parallelized image resizing.
long int sc_carve_paral_progress(void)
Queries the parallelized image resizing progress.

Code Example

The resize_image function imitates sc_carve but operates with T = 4. Again, starting the threads and waiting for them to finish is done by the start_thread and join_thread pesudo functions which use the thread_t pseudo data type. Such a functionality provides the pthreads library, for example.

Build Notes

Library Functions Include Header

The include header is "seamcarv.h".

C99 And bool

The library functions are written in C99 and use the bool data type. This is available through the <stdbool.h> C99 include header. When compiling with GCC the command line parameter -std=c99 may be required. If the source code uses non-stdlib functions, the additional GCC command line parameter -U__STRICT_ANSI__ may be required to clear the __STRICT_ANSI__ preprocessor macro.

Linking Against The Library

Note: I highly recommend to see the GCC manual.
In order to dynamically link the program using the Fugenschnitzer program library by GCC muß folgendes erfüllt sein:

  1. The library must be placed in the library search path or in the same directory as the source/object code. The library is a single file named:
    Platform Library File Name
    Windows seamcarv.dll
    Darwin/OS X libseamcarv.dylib
    Linux libseamcarv.so
  2. The library name and maybe the current directory must be added as a link-time library search path:
    -lseamcarv -L.
  3. On Linux the run-time library search path must be extended by the current directory:
    -Wl,-R.

The complete command line for Linux is therefore (further libraries may be added):
> gcc example.c -std=c99 -U__STRICT_ANSI__ -lseamcarv -L. -Wl,-R. -o example
Note: If GCC pretends not to find the library although it is obviously there, see the GCC manual, section Options For Linking about the procedure GCC uses to look for the library, how the library must be named and how link-time and run-time library search parameters are added to the command line. Further information and much more is also available from the ld manual which is the GNU linker, invoked by GCC when linking.