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
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.
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)
.
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.
-
Return value:
-
false: Everything is fine.
-
true: Fatal error: Memory allocation
(malloc) failed.
- image: Image data as 1D pixel array.
-
width, height: Image measures in pixels. For
zoom > 1, these are changed to the preview image measures
(integer division by
zoom).
-
zoom: Scale factor for the preview image.
If not required, set zoom = 0.
-
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.
-
Return value:
-
0: The image has not been extended.
-
1: The image has not been extended. That means that
the invoking program must allocate additional memory in order to
be able to retrieve the enlarged image later.
The image memory must be enlarged to
width * height *
sizeof(comp_t)
.
-
-1: Fatal error: Memory allocation
(malloc) failed.
-
vertical: Set to true if the image
should be resized in vertical direction.
-
extend: Tells by how much pixels
the image should be able to be resized at most. If the image
should only be shrinked, set extend = 0.
-
interpol: If the image should get larger than
its original, image pixels must be inserted.
With interpol = true the two neighbour pixels'
channel-wise average value is used. Otherwise, the preceeding
neighbour pixel's value is copied.
-
width, height: Outputs the image measure of the
maximally enlarged image. These differ by extend
in the image resizing direction from the original measures.
If, for example, vertical = false and extend
= 50 are given, width will be increased by 50
while height remains at the same value.
-
pwidth, pheight: Like width,
height but for the preview image. For
zoom > 1 in sc_load (above)
these values correspond to the returned values for
width and height, divided by
zoom.
- bool sc_seam(long int last)
-
Computes last seams.
-
Return value:
-
false: Everything is fine.
-
true: The operation was cancelled because
either last exceeds the image measures or
sc_seam_cancel was called while
the seam computation was running.
-
last: Tells how much seams should be computed.
The absolute value of last is used.
-
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.
-
Return value: Returns the actual value of the image size difference
of the resized image. The returned value only differs from the nominal value
nom if either the desired amount of resizing exceeded the
number of seams computed so far or it was tried to enlage the image more
than it was extended before by sc_prepare through the
extend parameter.
-
nom: Sets the nominal value for
the size difference between the resized and the original image.
-
width, height: Outputs the actual image measures
of the resized image in pixels.
-
pwidth, pheight: Outputs the actual preview image measures
of the resized image in pixels.
-
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
-
Return value:
- false: Everything is fine.
-
true: Fatal error: Memory allocation
(malloc) failed.
-
restore: Set to true if
image resizing should be reverted before fixing. Then the
image's original state is restored.
-
width, height: Outputs the image measures
after fixing in pixels.
-
pwidth, pheight: Outputs the preview image measures
after fixing in pixels.
- void sc_eject(comp_t *image)
- Outputs the image.
- void sc_close(void)
- Closes everything.
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.
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.
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.
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.
-
For the form only, two further variables for the preview image size
are required. We are not going to use this functionality, thus, these
variables will never be evaluated. Anyway, we need them for the
library functions:
long int px, py;
-
Here we go. First we call sc_init:
sc_init();
-
Now load the image:
sc_load(image, &x, &y, 0);
-
Prepare for seam computation, giving to sc_prepare
- horizontal direction and
- extension by 50 Pixels and
- turn on pixel interpolation:
sc_prepare(false, 50, true, &x, &y, &px,
&py);
-
Since the image will grow larger, we need to extend the image memory.
x and y just have been changed by
sc_prepare to the maximum new image size:
image = realloc(image, x * y *
sizeof(comp_t));
-
Now we can compute the seams and immediately resize the image:
sc_seam(50);
sc_carve(50, &x, &y, &px,
&py);
-
We now have to fix the resized image, after that we can retrieve it:
sc_fix(false, &x, &y, &px,
&py);
sc_eject(image);
-
Finish the procedure:
sc_close();
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.
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:
-
From beginning to sc_prepare call followed by
realloc as above.
-
Assumed the user first wants to resize the image to
(original width minus 10) pixels:
sc_seam(-10); // sc_seam will use the absolute value of -10
and compute 10 seams.
sc_carve(-10, &x, &y, &px,
&py);
sc_eject(image);
-
Now we can display the image. Attention: The image output by
sc_eject has a width of (original width + 50) pixels because we set
extend = 50 when we called sc_prepare. But only
(original width – 10) of these are valid, the rest is garbage.
-
Now the user wants to resize the image to (original width plus 25):
sc_seam(25); // sc_seam will now compute 15 more seams
because 10 have been computed already.
sc_carve(25, &x, &y, &px,
&py);
sc_eject(image);
-
Again we display the image. Now (original width + 25) of
the total (original width + 50) pixels in each line are valid.
-
This can go on more times. The user can resize the image at
most to (original width + 50) pixels; at least 3 pixels are possible
(theoretically 0, to be implemented ;). If he decides to resize the image to
(original width + 50) pixels, all pixels in each line are valid.
-
When the user is finished, we fix the image by calling
sc_fix. The spare pixels each line will be removed,
resulting in image containing the whole imagein the new size.
After that we continue as in the example above.
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.
-
long int sc_seam_progress(void)
-
Queries the progress of a running seam computation.
-
Return value: The absolute value corresponds to the
index of the seam currently computed.
- positive sign: Seam computation is running.
- negative sign: Seam computation has been finished or cancelled.
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.
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:
- simultaneous differentiation
-
accumulation of differentiated image lines while simultaneously differentiating
the following ones
- simultaneously applying the computed seam to several image parts
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:
- sc_seam_paral_diff
- sc_seam_paral_accu
- sc_seam_paral_seam
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.
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:
- sc_seam_paral_init
- (seam computation counting loop)
- 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:
- sc_seam_paral_start
-
(differentiation loop, several differentiation threads) →
synchronizing → (accumulation loop)
- sc_seam_paral_seam_init
- sc_seam_paral_seam (runs in multiple threads simultaneously)
- sc_seam_paral_finish
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:
- Start a thread,
- wait for one or more threads to finish,
- send an integer value message from one thread to another,
- 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.
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.
- Return value: Returns the number of image parts.
-
samples: Sets the desired number of pixels per image part.
For samples = 0 the default value 65536 is used.
The value is rounded up to an integer multiple of the line width:
If, for example, the image width is 1000, it will be rounded up to 66000.
-
threads: Sets the number of clips/threads on which
the differentiation process of one image part is distributed. For
threads = 0 one single thread is used.
-
void sc_seam_paral_diff(
const int part,
const int thread
)
-
Differentiation function for parallelized seam computation.
-
part: Sets the index of the image
part to differentiate.
-
thread: Sets the index of the differentiation thread.
-
bool sc_seam_paral_accu(const int part)
-
Accumulation function of the parallelized seam computation.
-
Return value:
- false: Computation is hanging.
- true: Operation finished.
-
part: Sets the index of the image
part to accumulate.
-
void sc_seam_paral_seam_init(const int
threads)
-
Initializes processing the current seam.
-
threads: Sets the number of processing threads.
-
void sc_seam_paral_seam(const int thread)
-
Seam processing function.
-
thread: Sets the processing thread index.
-
long int sc_seam_paral_finish(void)
-
Finishes the parallelized computation of the current seam.
-
Return value: Returns the index of the computed seam.
- void sc_seam_paral_close(void)
- Finihes the seam computation.
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.
- S is the index of the last seam to compute.
-
T is the number of threads which is arbitrarily set to
T = 4.
-
P is the number of image parts and is returned by
sc_seam_paral_start.
Library functions are marked up bold, variable identifiers variable-styled
and pseudo functions/data types italic.
- void diff_loop(const int T) {
- thread_t thread[T];
int P = sc_seam_paral_start(0, T);
-
for (int p = 0; p < P; p++) {
-
for (int t = 0; t < T; t++)
-
-
thread[t] =
start_thread(sc_seam_paral_diff(p,
t));
-
for (int t = 0; t < T; t++)
´
-
- send_message(p);
}
}
- void accu_loop(void) {
-
- bool finished;
-
do {
- int p = wait_for_message();
- finished = sc_seam_paral_accu(p);
} while (!finished);
- }
-
int compute_seams(const int S) {
- const int T = 4;
- int s;
-
thread_t diffth, accuth,
seamth[T];
sc_seam_paral_init();
-
do {
-
diffth =
start_thread(diff_loop(T));
-
accuth = start_thread(accu_loop());
- join_thread(accuth);
- join_thread(diffth);
sc_seam_paral_seam_init(T);
-
for (int t = 0; t < T; t++)
-
-
seamth[t] =
start_thread(sc_seam_paral_seam(t));
-
for (int t = 0; t < T; t++)
-
s = sc_seam_paral_finish();
} while (s != S);
sc_seam_paral_close();
}
The image resizing operation can also be parallelized. This is done according to the following scheme:
-
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).
-
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.
-
After all instances of sc_carve_paral are finished, finish the operation
by calling sc_carve_paral_finish.
While sc_carve_paral is running—optionally in several instances
simultaneously—,
the invoking program may query the progress by calling
sc_carve_paral_progress.
-
long int sc_carve_paral_init(
long int nom,
int threads
)
-
Initializes parallelized image reszing.
-
Return value:
Returns the number of image lines (horizontal) or rows (vertical) to be processed.
-
nom: As nom for sc_carve.
-
threads:
Tells how many instances of
sc_carve_paral
will be invoked for resizing.
For threads = 0 on single thread is used.
-
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.
-
Return value and parameters as for sc_carve.
-
long int sc_carve_paral_progress(void)
-
Queries the parallelized image resizing progress.
-
Return value:
-
0 or above:
Returns the number of processed image lines or rows so far.
This value is in the range from
0 to (sc_carve_paral_init return value – 1)
-
– 1: Currently no instance of sc_carve_paral is runnning.
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.
- long int resize_image(
- long int nom,
- long int *width, long int *height,
- long int *pwidth, long int *pheight
) {
- const int T = 4;
- thread_t thread[T];
sc_carve_paral_init(nom, T);
-
for (int t = 0; t < T; t++)
-
-
thread[t] =
start_thread(sc_carve_paral(t));
-
for (int t = 0; t < T; t++)
-
return sc_carve_paral_finish(
- long int *width, long int *height,
- long int *pwidth, long int *pheight
);
}
The include header is "seamcarv.h".
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.
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:
-
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 |
-
The library name and maybe the current directory must be
added as a link-time library search path:
-lseamcarv -L.
-
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.