Introduction

Abstract

Curvature flow equations smoothen images by smoothing their level lines. In contrast to linear smoothing filters, they do not only conserve sharp edges, but also have some remarkable properties like contrast invariance, or affine invariance. This filter resembles some recently discovered approximation schemes that (more or less) inherit many of those properties.

Common smoothing algorithms are often approximations of the heat equation applied to an image — in most cases realized by convolution with some smartly choosen kernel. This kind of smoothing removes (or "smears out") noise, but originally sharp edges become unlocatable. Moreover there are kinds of noise like impulse noise (also called Salt'n'Pepper noise) where the heat equation fails. Nonlinear filters like the well-known Median filter usually give better results. Sharp edges are untouched, but even nasty impuls noise can be removed satisfyingly. The Median filter is an approximation of the mean curvature flow — a mathematical object which smoothes the level lines of an image.

This filter collection provides several approximations of curvature flow filters, including the Median. These filters are realized by combining discrete erosions and dilations (operators that replace pixels with neighbor pixels that are darker or brighter, resp.) with several (nonlinear convolution) kernels, and resemble not only the mean curvature flow, but also the affine curvature flow, which gives usually even better results. The user may choose between a pure morphological approach, where no new color values are created, and an "almost-morphological" approach where the average value of erosions and dilations will be returned.

This plugin is designed to work with AviSynth 2.5 and is able to process all color spaces (RGB, RGBA, YV12, YUY2), although YUV color spaces are recommended.

Terms and Conditions for Execution, Copying, Distribution and Modification

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 2, as published by the Free Software Foundation in June 1991 (see 'GNUGPLv2.txt').

There is no guaranty that the rights of third parties (including software patents) are not infringed upon by the execution or distribution of this program. Referring to section 8 of the General Public License, any use of this program (including all activities mentioned in section 0 and including execution) is restricted to countries where any of these activities do not infringe upon any such rights of third parties. It lies with the user to verify the compliance of his or her use (especially concerning but not limited to distribution) of this program with the rights of any third parties in the respective countries or regions.

This program is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License 2 along with this program; if not, write to the

Usage

Loading the plugin

You need the files AviSynth_C.dll and AVSCurveFlow.dll in your working directory. To load the plugin, your script should start with the following lines:

LoadPlugin("AviSynth_C.dll")
LoadCPlugin("AVSCurveFlow.dll")

Curveature Flow filter functions

CurvatureFlow(clip Clip, Type, string Mode, int "Steps")
MeanCurvatureFlow(clip Clip, int "Steps")
AffineCurvatureFlow(clip Clip, int "Steps")

CurvatureFlow applies a curvature flow smoothing filter to the source clip.

• Clip gives the source clip. The resulting clip will have the same properties as the source clip. All color spaces (RGB, RGBA, YV12, YUY2) are allowed, but YUV color spaces are recommended: Each luma value will be accompanied by its chroma values. In RGB spaces all channels will be processed independently and spurious colors might appear.

• Type will determine the kind of curvature flow approximation used. This argument takes string values as well as integers. Integers may be in the range -1 .. 9:

  -1	Discrete 3×3 median filter
  0	Mean Curvature Flow approximation by Catté et al. (see below).
  1 .. 9	Affine Curvature Flow approximation by Boiger & Bornemann (see below). The actual number defines an area which determines the way the erosions and dilations will behave. As mentioned later, type 3 is in most cases the best choice for denoising a video. Type 1 results in a filter not changing the video in any way (a fact known to the plugin, so no unnecessary computation will be performed), whereas the types 8 and 9 will both give the full (3×3 pixel) erosion / dilation operator.

  For convenience, some values may be abbreviated by text strings. The following text strings are used synonymously to the numeric values given above:

  roman numbers "I" .. "VIII"	They have the same meaning as their decimal counterpart 1 .. 8
  "MED", "MEDIAN"	Synonym for the Median filter value -1
  "MCF", "MCM"	Synonym for the Mean Curvature Flow approximation 0
  "ACF", "AMSS"	Synonym for the Affine Curvature Flow approximation 3
  "INFO"	Not a synonym. Will return a copyright message (as error).

  All these string arguments are not case-sensitive.

  Please note: In most cases ACF, MCF and MED give the best results, while all other types are only supported for completeness and have rare applications.

• Mode defines the order in which the erosion and dilation operators given by Type are applied. The following modes are permitted:

  "M", "MEAN"	In each iteration step, the erosion and dilation are applied independently and their mean value is used for the next iteration step. This is the only non-morphological mode, which means it does not commute with AviSynth's Levels function.
  "D"	Will only apply dilations (the image gets brighter)
  "E"	Will only apply erosions (the image gets darker)
  "ED", "C"	Will apply dilations and erosions alternating, the dilation being first in each step. This combination of dilations and erosions is also called Closing.
  "DE", "O"	Will apply dilations and erosions alternating, the erosion being first in each step. This combination of dilations and erosions is also called Opening.

  All these string arguments are not case-sensitive.

  There is no general recommendation for the Mode argument: While O and C become stationary after a few interations (hence the number if iterations steps is effectively limited), the M mode tends to produce some blur near edges that are not parallel to pixel symmetry axes.

  Please note that erosions and dilations coincide if the median filter is choosen. In this case, the Mode argument is ignored.

• Steps gives the number of iteration steps. Each steps is performed by applying a dilation and/or erosion determined by the Type argument in the order defined by the Mode argument. (Default: 1). Increasing Steps usually increases the smoothing effect of the filter. Nevertheless, most images become stationary after applying a couple of iterations.

MeanCurvatureFlow(clip Clip, int "Steps") is an abbreviation of CurvatureFlow(Clip,"MCF","MEAN",Steps).
AffineCurvatureFlow(clip Clip, int "Steps") is an abbreviation of CurvatureFlow(Clip,"ACF","MEAN",Steps).

Sample Scripts

This script opens a video file and applies the affine curvature flow. This is always a good first try when denoising a video:

LoadPlugin("AviSynth_C.dll")
LoadCPlugin("AVSCurveFlow.dll")

AVISource("MyMovie.avi")
ConvertToYUY2
AffineCurvatureFlow(2)

This script applies the classical closing operator, which should remove some black dirt (if there is any):

LoadPlugin("AviSynth_C.dll")
LoadCPlugin("AVSCurveFlow.dll")

AVISource("MyMovie.avi")
ConvertToYUY2
CurvatureFlow(8,"C",2)

LoadPlugin("AviSynth_C.dll")
LoadCPlugin("AVSCurveFlow.dll")

AVISource("MyMovie.avi")
ConvertToYUY2
CurvatureFlow(8,"D",4)
CurvatureFlow(8,"E",4)

Mathematical Background

In the following Du denotes the gradient of a gray level image u:R²→R, and D²u its Hessian. When the task of smoothing an image comes up a common tool is the heat equation:

The following remarks aren't mathematically exact, but rather an outline of the details, that are needed to understand the implementation.

Morphological Scale Space Operators

One of these assumptions is morphology: The operator T_t is translation invariant and commutes with contrast transformations. A contrast transformation g is defined by a nondecreasing function g:R→R and applied to an image u through:

A core result of [AGLM] shows that satisfying some special assumptions, including morphology, T_t is the propagator of this general partial differential equation (which will be referred as (PDE) in the sequel):

Geometrical Curvature Flow Equations

If an image evolves accordingly to (PDE), the level lines of the image follow the geometric curvature flow equation:

Approximation Schemes

One way to apply these equations to pixel images is to approximate the right hand side of (PDE) with finite differences. Unfortunatelly it has turned out that there is no way to create a (reasonable) monotone finite difference scheme. In the last years, several approximation schemes for the mentioned equations have been developed following a morphological approach. These filters are compositions of a dilation-type and an erosion-type operator which on their part act on 3×3 pixel blocks. Erosions and dialtions are usually written as

In [CDK], such a family F is presented, and it is shown, that a proper combination of the resulting operators is consistent with the mean curvature flow. There is also a natural way presented how this family can be discretizised on the 3×3 pixel block.

In [BB], another family of sets is presented, which is then proven to create an operator consistent with the affine curvature flow. There is also a discretization on the 3×3 pixel block, which results in eight different approximations, depending on a special area parameter that may vary between 0 and 4.5. If this area is below 0.5, the operators become the identity operator. If this area is above 3.5, the corresponding discrete family F only consists of the full 3×3 pixel block, hence the paricular erosion and dilation operator represent the full (classical) morphological erosion and dilation, respectively. As numerical experiments in [BB] show, choosing an area of 1.5 yields best results when denoising impulse noise.

Another morphological approximation scheme for the mean curvature flow is the median operator. The discretization is obvious: Replace each pixel by the median value of its 3×3 neightborhood. This operator can be interpreted as dilation and erosion as well.

Fast Implementation

All discrete (3×3 pixel) erosions and dilations choose one of nine pixels and replace the center pixel with this new value. This choice only depends on the order of the values. To exploit this fact, the implementation prepares a look-up table for each morphological operator where all possible orders are listed together with their respective choice. When a pixel is processed, the order of its neighborhood values is determined and the table is used to determine which value is the new one of the pixel. In the actual implementation as AviSynth plugin, these tables are built upon invokation of the filter function in the script. A table once built will not be build again until the script is closed (and the script environment is destroied). If another filter in the same environment needs a table which has already been built, this table will be reused.

To further reduce the computational effort of sorting pixels, two pixel blocks (twelve pixels) are always processed toghether (what doubles the size necessary for a look-up table).

Only grayscale images have been considered so far. When a YUV image is processed, the choice described above is made on the basis of the Y channel. Then all channels are updated based on this choice. Hence luma and chroma values are transported the same way. In contrast to this, each channel of an RGB image will be treated separately, so in general different color spaces of equal images can give completely different results.

References

Version History