LIC -- Line Integral Convolution

Andreas Hirczy

Die klassischen Verfahren zur Visualisierung von Vektorfeldern sind bei Feldgrößen größer als $10\times 10$ nur schwer zu interpretieren. Die Pfeile, mit denen Felder häufig angezeigt werden, benötigen zu viel Platz auf dem Display. Berechnung von Stromlinien von bestimmten, zufälligen Punkten aus haben den Nachteil, daß man niemals sicher sein kann, die interessanten Bereiche des Strömungsfeldes überhaupt zur erreichen.

Zur Analyse großer Vektorfelder werden globale Verfahren benötigt, die die Feldrichtung überall in einem Feld anzeigen.

1993 [1] wurde die ,,line integral convolution`` vorgestellt, bei dem die Richtungsinformation des Feldes in jedem Punkt einer Rastergraphik dargestellt werden kann. Dabei wird ein Feld, das mit weißem Rauschen vorbelegt wurde, entlang der Feldlinien gemittelt. Punkte auf der selben Feldlinie haben daher eine wesentlich größeren Ähnlichkeit als Punkte auf nebeneinander liegenden Feldlinien.

Die LIC hat allerdings mehrere wesentliche Nachteile:

(lange) Laufzeit:

keine Möglichkeit zur interaktiven Bearbeitung

keine direkte Anzeige der Feldstärke:

Abhilfe ist durch Verwendung von Farben möglich.

Vor- und Rückwärtsrichtung sind nicht unterscheidbar:

Durch Erstellung eines Films kann sowohl die Orientierung der Feldlinien als auch ihre Stärke sichtbar gemacht werden. Zu diesem Thema kann bei Stalling und Hege [2] näheres gelesen werden.

Optimierungen

Unsere erste Implementierung der LIC wurde in kürzester Zeit in Matlab geschrieben. Die Laufzeit von ungefähr 6 Stunden auf einer DEC Alpha Workstation für ein Feld von $100\times 100$ Punkten legt den Gedanken an Optimierungen nahe.

lineare Interpolation:

Bereits das Ersetzen der ursprünglich kubischen Interpolation durch eine lineare Interpolation unter Ausnützung des äquidistanten Rasters im ursprünglichen Matlab-Code brachte einen Performancegewinn von etwa 2.

Verwendung von C/C++:

Die Berechnung kann auch in Matlab nicht ohne die intensive Verwendung von Schleifen programmiert werden. Der Interpreter führt dabei zu massiven Zeitverlusten.

Verzicht auf Interpolation:

Die Anordnung der Punkte in einem äquidistantem Raster erlaubt die Verwendung eines einfacheren Algorithmus an Stelle der Euler-Integration zur Verfolgung der Stromlinien.

Bei jedem Schritt der Intergration können innerhalb der Matrix nur 8 Nachbarfelder erreicht werden. Weil die Mittelpunkte benachbarte Felder, die nur eine Ecke teilen um $2$ näher sind als Felder, die eine Kante teilen, wurden die Übertrittswahrscheinlichkeiten entsprechend angesetzt.

Die Summe dieser Maßnahmen mit einigen C++-spezifischen Optimierungen führt zu einer Laufzeit von 3.5 Sekunden auf einem PC486DX2/66 mit 32MBRAM und 0.33 Sekunden auf einem PCPentium 200/MMX mit 128MBRAM unter Linux.

Anbindung von C und C++ an Matlab

Die Anbindung eigener Routinen in C, C++ und Fortran an Matlab wird durch einen Mechanismus namens MEX (Matlab EXtensions) vorgenommen. Die enstprechenden Funktionen beginnen mit dem Präfix ,,mex``; Funktionen zum Zugriff auf Matrizen mit dem Präfix ,,mx``.

indentation

// Includes:
#include mex.h$>$
#include assert.h$>$
#include unistd.h$>$
#include math.h$>$

static int nrRows, nrCols; // number of rows, number of columns
double $*$vx, $*$vy; // pointer to convolution matrices
double $*$oriNoise, $*$oriHue; // pointer to input matrices
double $*$conNoise, $*$conHue; // pointer to output matrices
double $*$angle;
double h; // stepsize for integrator
int num; // length of convolution kernel

inline double
getElem(const double $*$aArr, const int aRow, const int aCol)
{
assert((aRow $\ge$ 0)&&(aRow nrRows));
assert((aCol $\ge$ 0)&&(aCol nrCols));

return $*$(aArr + aCol$*$nrRows + aRow);
};

inline void
setElem(double $*$aArr, const int aRow, const int aCol, const double aVal)
{
assert((aRow $\ge$ 0)&&(aRow nrRows));
assert((aCol $\ge$ 0)&&(aCol nrCols));

$*$(aArr + aCol$*$nrRows + aRow) = aVal;
};

#define IN_VX prhs[0]
#define IN_VY prhs[1]
#define IN_NOISE prhs[2]
#define IN_HUE prhs[3]
#define IN_H prhs[4]
#define IN_NUM prhs[5]

#define OUT_LIC_NOISE plhs[0]
#define OUT_LIC_HUE plhs[1]

void
mexFunction(int nlhs, mxArray $*$plhs[],
int nrhs, const mxArray $*$prhs[])
{
// Check for proper number of arguments
if (6 $\ne$ nrhs)
mexErrMsgTxt("Requires six input arguments.");
if (2 $\ne$ nlhs)
mexErrMsgTxt("Requires two output arguments.");

// Check dimensions (TODO: check all matrices)
nrRows = mxGetM(IN_NOISE);
nrCols = mxGetN(IN_NOISE);

mexPrintf("Matrix size: %d rows and %d columns$$n", nrRows, nrCols);

// create matrices for return arguments
OUT_LIC_NOISE = mxCreateDoubleMatrix(nrRows, nrCols, mxREAL);
OUT_LIC_HUE = mxCreateDoubleMatrix(nrRows, nrCols, mxREAL);

// assign pointers to parameters
vx = mxGetPr(IN_VX);
vy = mxGetPr(IN_VY);
oriNoise = mxGetPr(IN_NOISE);
oriHue = mxGetPr(IN_HUE);
h = mxGetScalar(IN_H);
num = int(floor(mxGetScalar(IN_NUM)));
conNoise = mxGetPr(OUT_LIC_NOISE);
conHue = mxGetPr(OUT_LIC_HUE);

// do the computations in a subroutine
lic_field();

return;
};

Die Datei mit dem C/C++-Programm wird durch den Befehl

mex -g <dateinahme.c>

oder

mex -O <dateinahme.c>

kompiliert. Die entstehende Datei trägt unter Linux die Endung ,,.mexln``. Sie wird in den Pfad für Matlab-Dateien kopiert und kann sofort verwendet werden.

Wenn eine Online-Hilfe nach Matlab Standard geschrieben werden soll, muß zusätzlich ein gleichnamiges M-File geschrieben werden. Matlab holt dann die Beschreibung aus dem M-File und den Code aus dem Mex-File.

Sourcen

Die verwendeten Dateien können im Format .tar.gz und.zip geladen werden.

Literatur

1

CHABRAL, Brian ; LEEDOM, Leith C.:
Imaging Vector Fields Using Line Integral Convolution.
In: Proceedings of SIGGRAPH '93.
New York, 1993, S. 263-270

2

STALLING, Detlef ; HEGE, Hans-Christian:
Fast and Resolution Independent Line Integral Convolution.
In: Proceedings of SIGGRAPH '95.
New York, 1995, S. 249-256

Über dieses Dokument ...

LIC -- Line Integral Convolution

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -html_version 3.2,math -split 0 -no_navigation LIC.tex.

The translation was initiated by on 9/4/1998