[vlc-devel] [PATCH 2/6] Add monotone cubic interpolation support
Ronald Wright
logiconcepts819 at gmail.com
Thu Jul 24 19:19:18 CEST 2014
---
include/vlc_interpolation.h | 122 ++++++++++++++++++++++++
po/POTFILES.in | 2 +
src/Makefile.am | 2 +
src/libvlccore.sym | 3 +
src/misc/interpolation.c | 219 ++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 348 insertions(+)
create mode 100644 include/vlc_interpolation.h
create mode 100644 src/misc/interpolation.c
diff --git a/include/vlc_interpolation.h b/include/vlc_interpolation.h
new file mode 100644
index 0000000..58c491b
--- /dev/null
+++ b/include/vlc_interpolation.h
@@ -0,0 +1,122 @@
+/*****************************************************************************
+ * vlc_interpolation.h: Interpolation utility
+ *****************************************************************************
+ * Copyright (C) 2014 Ronald Wright
+ * $Id$
+ *
+ * Author: Ronald Wright <logiconcepts819 at gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
+ *****************************************************************************/
+
+#ifndef VLC_INTERPOLATION_H
+#define VLC_INTERPOLATION_H
+
+/**
+ * \file
+ * This file is the interface definition for a modification of Fritsch-Carlson
+ * monotone cubic spline interpolation (implementation in
+ * src/misc/interpolation.c)
+ */
+
+/*****************************************************************************
+ * Documentation
+ *****************************************************************************/
+/*
+ **** Background
+ *
+ * This implements a modification of Fritsch-Carlson monotone cubic spline
+ * interpolation. Fritsch-Carlson interpolation creates an interpolant as
+ * follows:
+ *
+ * 1. The slopes between successive data points are computed.
+ * 2. The tangents at each data point is computed as the average of the
+ * secants.
+ * 3. To preserve monotonicity, slopes are set to zero wherever two successive
+ * points are equal.
+ * 4. To prevent overshoot, two successive slopes, normalized by the tangent
+ * at the leftmost point, are restricted so that the sum of their squares do
+ * not exceed a certain threshold (9 in this algorithm).
+ *
+ * The interpolation is modified such that all sample points left of the spline
+ * have values equal to the left-most data point and all sample points right of
+ * the spline have values equal to the right-most data point. Hence, the
+ * resulting line extending outward from the left-most data point has zero
+ * slope, and the resulting line extending outward from the right-most data
+ * point has zero slope.
+ *
+ **** Example usage
+ *
+ * #define NUM_POINTS 4
+ * ...
+ * my_function()
+ * {
+ * ...
+ * float points[NUM_POINTS] = { -0.5, 1.0, 2.5, 5.0 };
+ * float values[NUM_POINTS] = { 8.0, -5.0, 0.0, 3.0 };
+ * ...
+ * vlc_interpolant_t itp;
+ * if( vlc_create_interpolant( points, values, NUM_POINTS, &itp ) == VLC_SUCCESS )
+ * {
+ * ...
+ * float y = vlc_interpolate( &itp, 0.5 );
+ * ...
+ * vlc_destroy_interpolant( &itp );
+ * ...
+ * }
+ * ...
+ * }
+ * */
+
+/*****************************************************************************
+ * Interpolant type
+ *****************************************************************************/
+
+typedef struct
+{
+ float * pf_points;
+ float * pf_values;
+
+ float * pf_c1s;
+ float * pf_c2s;
+ float * pf_c3s;
+
+ int i_point_count;
+} vlc_interpolant_t;
+
+/*****************************************************************************
+ * Interpolation routines
+ *****************************************************************************/
+
+/*
+ * Create a new interpolant from the given data points and data point values.
+ */
+VLC_API int vlc_create_interpolant( vlc_interpolant_t * p_interpolant,
+ const float * pf_points,
+ const float * pf_values,
+ int i_point_count );
+
+/*
+ * Sample the spline at the given sample point.
+ */
+VLC_API float vlc_interpolate( const vlc_interpolant_t * p_interpolant,
+ float f_sample_point );
+
+/*
+ * Destroy an interpolant that is no longer in use.
+ */
+VLC_API void vlc_destroy_interpolant( vlc_interpolant_t * p_interpolant );
+
+#endif
diff --git a/po/POTFILES.in b/po/POTFILES.in
index 09b2369..4a0405d 100644
--- a/po/POTFILES.in
+++ b/po/POTFILES.in
@@ -26,6 +26,7 @@ include/vlc_httpd.h
include/vlc_image.h
include/vlc_input.h
include/vlc_interface.h
+include/vlc_interpolation.h
include/vlc_intf_strings.h
include/vlc_iso_lang.h
include/vlc_keys.h
@@ -112,6 +113,7 @@ src/misc/es_format.c
src/misc/events.c
src/misc/filter_chain.c
src/misc/image.c
+src/misc/interpolation.c
src/misc/md5.c
src/misc/messages.c
src/misc/mtime.c
diff --git a/src/Makefile.am b/src/Makefile.am
index fbe7ec2..82a3b63 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -56,6 +56,7 @@ pluginsinclude_HEADERS = \
../include/vlc_inhibit.h \
../include/vlc_input.h \
../include/vlc_input_item.h \
+ ../include/vlc_interpolation.h \
../include/vlc_keys.h \
../include/vlc_main.h \
../include/vlc_md5.h \
@@ -439,6 +440,7 @@ SOURCES_libvlc_common = \
misc/block.c \
misc/fourcc.c \
misc/es_format.c \
+ misc/interpolation.c \
misc/picture.c \
misc/picture_fifo.c \
misc/picture_pool.c \
diff --git a/src/libvlccore.sym b/src/libvlccore.sym
index 325c8f6..29a204c 100644
--- a/src/libvlccore.sym
+++ b/src/libvlccore.sym
@@ -501,6 +501,8 @@ vlc_sem_destroy
vlc_sem_post
vlc_sem_wait
vlc_control_cancel
+vlc_create_interpolant
+vlc_destroy_interpolant
vlc_GetCPUCount
vlc_CPU
vlc_error
@@ -528,6 +530,7 @@ vlc_ngettext
vlc_iconv
vlc_iconv_close
vlc_iconv_open
+vlc_interpolate
vlc_join
vlc_list_children
vlc_list_release
diff --git a/src/misc/interpolation.c b/src/misc/interpolation.c
new file mode 100644
index 0000000..31c80d3
--- /dev/null
+++ b/src/misc/interpolation.c
@@ -0,0 +1,219 @@
+/*****************************************************************************
+ * vlc_interpolation.h: Interpolation utility
+ *****************************************************************************
+ * Copyright (C) 2014 Ronald Wright
+ * $Id$
+ *
+ * Author: Ronald Wright <logiconcepts819 at gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or
+ * (at your option) any later version.
+ *
+ * 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 Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
+ *****************************************************************************/
+
+/*****************************************************************************
+ * Preamble
+ *****************************************************************************/
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <vlc_common.h>
+#include <vlc_interpolation.h>
+
+/*****************************************************************************
+ * Documentation : Read vlc_interpolation.h
+ *****************************************************************************/
+
+/*****************************************************************************
+ * Implementation of interpolation routines.
+ *****************************************************************************/
+
+int vlc_create_interpolant( vlc_interpolant_t * p_interpolant,
+ const float * pf_points, const float * pf_values,
+ int i_point_count )
+{
+ /* This subroutine assumes that each sample point in the sequence
+ * referenced by pf_points is unique and that the sequence is sorted. */
+
+ /* We should have at least two data points for the computation */
+ if( i_point_count < 2 )
+ return VLC_EBADVAR;
+
+ int i_ret_val = VLC_ENOMEM;
+
+ /* Allocate memory */
+
+ float * pf_dys = malloc( ( i_point_count - 1 ) * sizeof( *pf_dys ) );
+ if( unlikely( !pf_dys ) )
+ goto return_i_ret_val;
+
+ float * pf_dxs = malloc( ( i_point_count - 1 ) * sizeof( *pf_dxs ) );
+ if( unlikely( !pf_dxs ) )
+ goto free_pf_dys;
+
+ float * pf_ms = malloc( ( i_point_count - 1 ) * sizeof( *pf_ms ) );
+ if( unlikely( !pf_ms ) )
+ goto free_pf_dxs;
+
+ float * pf_c1s = malloc( i_point_count * sizeof( *pf_c1s ) );
+ if( unlikely( !pf_c1s ) )
+ goto free_pf_ms;
+
+ float * pf_c2s = malloc( ( i_point_count - 1 ) * sizeof( *pf_c2s ) );
+ if( unlikely( !pf_c2s ) )
+ goto free_pf_c1s;
+
+ float * pf_c3s = malloc( ( i_point_count - 1 ) * sizeof( *pf_c3s ) );
+ if( unlikely( !pf_c3s ) )
+ goto free_pf_c2s;
+
+ float * pf_points_ = malloc( i_point_count * sizeof( *pf_points_ ) );
+ if( unlikely( !pf_points_ ) )
+ goto free_pf_c3s;
+
+ float * pf_values_ = malloc( i_point_count * sizeof( *pf_values_ ) );
+ if( unlikely( !pf_values_ ) )
+ goto free_pf_points;
+
+ /* Get consecutive differences and slopes */
+ for( int i = 0; i < i_point_count - 1; i++ )
+ {
+ float f_dx = pf_points[i + 1] - pf_points[i];
+ float f_dy = pf_values[i + 1] - pf_values[i];
+ pf_dxs[i] = f_dx;
+ pf_dys[i] = f_dy;
+ pf_ms[i] = f_dy / f_dx;
+ }
+
+ /* Get degree-1 coefficients */
+ pf_c1s[0] = pf_ms[0];
+ for( int i = 0; i < i_point_count - 2; i++ )
+ {
+ float f_m = pf_ms[i];
+ float f_mNext = pf_ms[i + 1];
+ float f_c1;
+ if( f_m * f_mNext <= 0 )
+ {
+ f_c1 = 0.0f;
+ }
+ else
+ {
+ float f_dx = pf_dxs[i];
+ float f_dxNext = pf_dxs[i + 1];
+ float f_common = f_dx + f_dxNext;
+ f_c1 = 3.0f * f_common / ( ( f_common + f_dxNext ) / f_m
+ + ( f_common + f_dx ) / f_mNext );
+ }
+ pf_c1s[i + 1] = f_c1;
+ }
+ pf_c1s[i_point_count - 1] = pf_ms[i_point_count - 2];
+
+ /* Get degree-2 and degree-3 coefficients */
+ for( int i = 0; i < i_point_count - 1; i++ )
+ {
+ float f_c1 = pf_c1s[i];
+ float f_m = pf_ms[i];
+ float f_invDx = 1.0f / pf_dxs[i];
+ float f_common = f_c1 + pf_c1s[i + 1] - f_m - f_m;
+ pf_c2s[i] = ( f_m - f_c1 - f_common ) * f_invDx;
+ pf_c3s[i] = f_common * f_invDx * f_invDx;
+ }
+
+ /* Set up structure */
+ memcpy( pf_points_, pf_points, i_point_count * sizeof( *pf_points ) );
+ memcpy( pf_values_, pf_values, i_point_count * sizeof( *pf_values ) );
+ p_interpolant->pf_c1s = pf_c1s;
+ p_interpolant->pf_c2s = pf_c2s;
+ p_interpolant->pf_c3s = pf_c3s;
+ p_interpolant->pf_points = pf_points_;
+ p_interpolant->pf_values = pf_values_;
+ p_interpolant->i_point_count = i_point_count;
+ i_ret_val = VLC_SUCCESS;
+ goto free_pf_ms;
+
+free_pf_points:
+ free( pf_points_ );
+free_pf_c3s:
+ free( pf_c3s );
+free_pf_c2s:
+ free( pf_c2s );
+free_pf_c1s:
+ free( pf_c1s );
+free_pf_ms:
+ free( pf_ms );
+free_pf_dxs:
+ free( pf_dxs );
+free_pf_dys:
+ free( pf_dys );
+return_i_ret_val:
+ return i_ret_val;
+}
+
+float vlc_interpolate( const vlc_interpolant_t * p_interpolant,
+ float f_sample_point )
+{
+ const float * pf_points = p_interpolant->pf_points;
+ const float * pf_values = p_interpolant->pf_values;
+
+ /* Here, the implementation is modified to give the closest endpoints for
+ * sample points that lie outside the spline region */
+ int i = p_interpolant->i_point_count - 1;
+ if( f_sample_point >= pf_points[i] )
+ {
+ return pf_values[i];
+ }
+ if( f_sample_point <= pf_points[0] )
+ {
+ return pf_values[0];
+ }
+
+ /* Use binary search to find the matching data value or the region where
+ * the matching value is to be interpolated */
+ int i_low = 0;
+ int i_high = i - 1;
+ while( i_low <= i_high )
+ {
+ int i_mid = ( i_low + i_high ) >> 1;
+ float f_point_here = pf_points[i_mid];
+ if( f_point_here < f_sample_point )
+ {
+ i_low = i_mid + 1;
+ }
+ else if( f_point_here > f_sample_point )
+ {
+ i_high = i_mid - 1;
+ }
+ else
+ {
+ return pf_values[i_mid];
+ }
+ }
+ i = i_high > 0 ? i_high : 0;
+
+ /* Interpolate */
+ float f_diff = f_sample_point - pf_points[i];
+ return pf_values[i] + f_diff * ( p_interpolant->pf_c1s[i]
+ + f_diff * ( p_interpolant->pf_c2s[i]
+ + f_diff * p_interpolant->pf_c3s[i] ) );
+}
+
+void vlc_destroy_interpolant( vlc_interpolant_t * p_interpolant )
+{
+ free( p_interpolant->pf_values );
+ free( p_interpolant->pf_points );
+ free( p_interpolant->pf_c3s );
+ free( p_interpolant->pf_c2s );
+ free( p_interpolant->pf_c1s );
+}
--
1.9.1
More information about the vlc-devel
mailing list