[vlc-devel] [PATCH 1/8] Add monotone cubic interpolation support

Ronald Wright logiconcepts819 at gmail.com
Tue Dec 1 14:57:19 CET 2015


---
 include/vlc_interpolation.h   | 127 +++++++++++++++++++++++++
 po/POTFILES.in                |   2 +
 src/Makefile.am               |   2 +
 src/libvlccore.sym            |   3 +
 src/misc/interpolation.c      | 216 ++++++++++++++++++++++++++++++++++++++++++
 test/Makefile.am              |   3 +
 test/src/misc/interpolation.c | 129 +++++++++++++++++++++++++
 7 files changed, 482 insertions(+)
 create mode 100644 include/vlc_interpolation.h
 create mode 100644 src/misc/interpolation.c
 create mode 100644 test/src/misc/interpolation.c

diff --git a/include/vlc_interpolation.h b/include/vlc_interpolation.h
new file mode 100644
index 0000000..48948da
--- /dev/null
+++ b/include/vlc_interpolation.h
@@ -0,0 +1,127 @@
+/*****************************************************************************
+ * vlc_interpolation.h: Interpolation utility
+ *****************************************************************************
+ * Copyright (C) 2015 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
+ * \brief Interface definition for monotone cubic spline interpolation
+ *        (implementation in src/misc/interpolation.c)
+ *
+ * \section background 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 are 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.
+ *
+ * \section example Example usage
+ *
+ * \code{.cpp}
+ * #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_interpolant_create( &itp, points, values, NUM_POINTS ) == VLC_SUCCESS )
+ *     {
+ *         ...
+ *         float y = vlc_interpolate( itp, 0.5 );
+ *         ...
+ *         vlc_interpolant_destroy( itp );
+ *         ...
+ *     }
+ *     ...
+ * }
+ * \endcode
+ */
+
+/*****************************************************************************
+ * Interpolant type
+ *****************************************************************************/
+
+/**
+ * The interpolant data type. This is a pointer to a private structure defined
+ * in misc/interpolation.c.
+ */
+
+typedef struct vlc_interpolant_t vlc_interpolant_t;
+
+/*****************************************************************************
+ * Interpolation routines
+ *****************************************************************************/
+
+/**
+ * Create a new interpolant from the given data points and data point values.
+ *
+ * \param pp_interpolant The object that shall hold interpolant data
+ * \param pf_points The set of data points (or data x-values) to use
+ * \param pf_values The set of data point values (or data y-values) to use
+ * \param i_point_count The number of points and values
+ * \retval VLC_SUCCESS Success
+ * \retval VLC_ENOMEM  Memory failure
+ * \retval VLC_EBADVAR Not enough data points to create the spline
+ */
+VLC_API int vlc_interpolant_create( vlc_interpolant_t ** pp_interpolant,
+                                    const float * pf_points,
+                                    const float * pf_values,
+                                    int i_point_count );
+
+/**
+ * Sample the spline at the given sample point.
+ *
+ * \param p_interpolant The object that holds interpolant data
+ * \param f_sample_point The point at which the spline is to be sampled
+ * \return The value of 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.
+ *
+ * \param p_interpolant The object that holds interpolant data
+ */
+VLC_API void vlc_interpolant_destroy( vlc_interpolant_t * p_interpolant );
+
+#endif
diff --git a/po/POTFILES.in b/po/POTFILES.in
index d3d3bb0..db9e4ca 100644
--- a/po/POTFILES.in
+++ b/po/POTFILES.in
@@ -25,6 +25,7 @@ include/vlc_gcrypt.h
 include/vlc_httpd.h
 include/vlc_image.h
 include/vlc_input.h
+include/vlc_interpolation.h
 include/vlc_intf_strings.h
 include/vlc_iso_lang.h
 include/vlc_keys.h
@@ -110,6 +111,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 67debfe..0d534ba 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -57,6 +57,7 @@ pluginsinclude_HEADERS = \
 	../include/vlc_input.h \
 	../include/vlc_input_item.h \
 	../include/vlc_interface.h \
+	../include/vlc_interpolation.h \
 	../include/vlc_keys.h \
 	../include/vlc_main.h \
 	../include/vlc_md5.h \
@@ -435,6 +436,7 @@ SOURCES_libvlc_common = \
 	misc/fourcc.c \
 	misc/fourcc_list.h \
 	misc/es_format.c \
+	misc/interpolation.c \
 	misc/picture.c \
 	misc/picture.h \
 	misc/picture_fifo.c \
diff --git a/src/libvlccore.sym b/src/libvlccore.sym
index 95152e8..f03e451 100644
--- a/src/libvlccore.sym
+++ b/src/libvlccore.sym
@@ -519,6 +519,8 @@ vlc_sem_destroy
 vlc_sem_post
 vlc_sem_wait
 vlc_control_cancel
+vlc_interpolant_create
+vlc_interpolant_destroy
 vlc_GetCPUCount
 vlc_CPU
 vlc_error
@@ -547,6 +549,7 @@ vlc_ngettext
 vlc_iconv
 vlc_iconv_close
 vlc_iconv_open
+vlc_interpolate
 vlc_poll_i11e
 vlc_read_i11e
 vlc_readv_i11e
diff --git a/src/misc/interpolation.c b/src/misc/interpolation.c
new file mode 100644
index 0000000..a14a652
--- /dev/null
+++ b/src/misc/interpolation.c
@@ -0,0 +1,216 @@
+/*****************************************************************************
+ * vlc_interpolation.h: Interpolation utility
+ *****************************************************************************
+ * Copyright (C) 2015 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
+ *****************************************************************************/
+
+/*****************************************************************************
+ *  Private types.
+ *****************************************************************************/
+
+struct vlc_interpolant_t
+{
+    float * pf_points;
+    float * pf_values;
+
+    float * pf_c1s;
+    float * pf_c2s;
+    float * pf_c3s;
+
+    int i_point_count;
+
+    float f_cs[];
+};
+
+/*****************************************************************************
+ * Implementation of interpolation routines.
+ *****************************************************************************/
+
+int vlc_interpolant_create( vlc_interpolant_t ** pp_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_segment_count = i_point_count - 1;
+
+    /* Allocate memory for pf_dys, pf_dxs, and pf_ms, which will all be arrays
+     * of length i_segment_count. */
+
+    float * pf_dys = malloc( 3 * i_segment_count * sizeof( *pf_dys ) );
+    if( unlikely( !pf_dys ) )
+        return VLC_ENOMEM;
+
+    float * pf_dxs = pf_dys + i_segment_count;
+    float * pf_ms = pf_dxs + i_segment_count;
+
+    /* Allocate memory for the interpolant struct and its data members. pf_c1s,
+     * pf_points_, and pf_values_ will be arrays of length i_point_count, and
+     * pf_c2s and pf_c3s will be arrays of length i_segment_count. */
+
+    vlc_interpolant_t * p_interpolant;
+    float * pf_c1s, * pf_c2s, * pf_c3s, * pf_points_, * pf_values_;
+
+    int i_ret_val = VLC_ENOMEM;
+    int i_data_len = 3 * i_point_count + 2 * i_segment_count;
+    int i_total_size = i_data_len * sizeof( *pf_c1s ) + sizeof( *p_interpolant );
+
+    p_interpolant = malloc( i_total_size );
+    if( likely( p_interpolant != NULL ) )
+    {
+        i_ret_val = VLC_SUCCESS;
+
+        pf_c1s = p_interpolant->f_cs;
+        pf_c2s = pf_c1s + i_point_count;
+        pf_c3s = pf_c2s + i_segment_count;
+        pf_points_ = pf_c3s + i_segment_count;
+        pf_values_ = pf_points_ + i_point_count;
+
+        /* Get consecutive differences and slopes */
+        for( int i = 0; i < i_segment_count; 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_segment_count - 1; 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_segment_count] = pf_ms[i_segment_count - 1];
+
+        /* Get degree-2 and degree-3 coefficients */
+        for( int i = 0; i < i_segment_count; 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;
+        *pp_interpolant = p_interpolant;
+    }
+    free( pf_dys );
+    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_interpolant_destroy( vlc_interpolant_t * p_interpolant )
+{
+    free( p_interpolant );
+}
diff --git a/test/Makefile.am b/test/Makefile.am
index b732acf..94428d1 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -19,6 +19,7 @@ check_PROGRAMS = \
 	test_libvlc_media_list \
 	test_libvlc_media_player \
 	test_src_config_chain \
+	test_src_misc_interpolation \
 	test_src_misc_variables \
 	test_src_crypto_update \
 	test_src_input_stream \
@@ -75,6 +76,8 @@ test_libvlc_media_player_SOURCES = libvlc/media_player.c
 test_libvlc_media_player_LDADD = $(LIBVLC)
 test_libvlc_meta_SOURCES = libvlc/meta.c
 test_libvlc_meta_LDADD = $(LIBVLC)
+test_src_misc_interpolation_SOURCES = src/misc/interpolation.c
+test_src_misc_interpolation_LDADD = $(LIBVLCCORE)
 test_src_misc_variables_SOURCES = src/misc/variables.c
 test_src_misc_variables_LDADD = $(LIBVLCCORE) $(LIBVLC)
 test_src_config_chain_SOURCES = src/config/chain.c
diff --git a/test/src/misc/interpolation.c b/test/src/misc/interpolation.c
new file mode 100644
index 0000000..54a2395
--- /dev/null
+++ b/test/src/misc/interpolation.c
@@ -0,0 +1,129 @@
+/*****************************************************************************
+ * interpolation.c: test VLC interpolation utility
+ *****************************************************************************
+ * Copyright (C) 2015 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.
+ *****************************************************************************/
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <vlc_common.h>
+#include "../src/misc/interpolation.c"
+#include "../modules/audio_filter/equalizer_presets.h"
+
+#include <stdio.h>
+#include "../../libvlc/test.h"
+
+static void test_bad_interpolant_param( void )
+{
+    /* This case tests whether vlc_interpolant_create correctly detects an
+     * invalid parameter.  vlc_interpolant_create returns VLC_EBADVAR if less
+     * than 2 sample points are given.  Here, we give it 1 sample point to see
+     * if vlc_interpolant_create returns VLC_EBADVAR as it should. */
+
+    vlc_interpolant_t * p_itp;
+
+    float f_points_1[1] = { 0.0, };
+    float f_values_1[1] = { 0.0, };
+
+    assert( vlc_interpolant_create( &p_itp, f_points_1, f_values_1, 1 ) == VLC_EBADVAR );
+}
+
+static bool values_close_enough( float f_value1, float f_value2 )
+{
+    /* Values rounded to the nearest tenth have a maximum error of 0.05 */
+    return fabsf( f_value1 - f_value2 ) <= 0.05f;
+}
+
+static void test_interpolation( const float * pf_points1,
+                                const float * pf_values1, int i_count1,
+                                const float * pf_points2,
+                                const float * pf_values2, int i_count2 )
+{
+    vlc_interpolant_t * itp;
+
+    assert( vlc_interpolant_create( &itp, pf_points1, pf_values1, i_count1 ) == VLC_SUCCESS );
+
+    for( int i = 0; i < i_count2; i++ )
+    {
+        float f_interp_value = vlc_interpolate( itp, pf_points2[i] );
+        assert( values_close_enough( f_interp_value, pf_values2[i] ) );
+    }
+
+    vlc_interpolant_destroy( itp );
+}
+
+static void load_with_true_frequencies( float * pf_table, int i_type )
+{
+    /* Remember: display frequencies are slightly different from the true
+     *           frequencies used in the filtering process, and the
+     *           interpolation points for interpolated preset values are the
+     *           true frequencies, not the display frequencies */
+    int i_band_count = EqzGetNumBandsByType( i_type );
+    for( int i = 0; i < i_band_count; i++ )
+    {
+        pf_table[i] = EqzGetTrueFrequency( i_type, i );
+    }
+}
+
+static void test_some_interpolants( void )
+{
+    /* Test interpolations of equalizer presets */
+    float true_vlc_freq_table_10b[EQZ_VLC10_BANDS_MAX];
+    float true_iso_freq_table_10b[EQZ_ISO10_BANDS_MAX];
+    float true_iso_freq_table_15b[EQZ_ISO15_BANDS_MAX];
+    float true_iso_freq_table_31b[EQZ_ISO31_BANDS_MAX];
+
+    load_with_true_frequencies( true_vlc_freq_table_10b, EQZ_VLC10_TYPE );
+    load_with_true_frequencies( true_iso_freq_table_10b, EQZ_ISO10_TYPE );
+    load_with_true_frequencies( true_iso_freq_table_15b, EQZ_ISO15_TYPE );
+    load_with_true_frequencies( true_iso_freq_table_31b, EQZ_ISO31_TYPE );
+
+    for( int i = 0; i < NB_PRESETS; i++ )
+    {
+        test_interpolation( true_vlc_freq_table_10b,
+                            eqz_preset_vlc_10b[i].f_amp, EQZ_VLC10_BANDS_MAX,
+                            true_iso_freq_table_10b,
+                            eqz_preset_iso_10b[i].f_amp, EQZ_ISO10_BANDS_MAX );
+
+        test_interpolation( true_vlc_freq_table_10b,
+                            eqz_preset_vlc_10b[i].f_amp, EQZ_VLC10_BANDS_MAX,
+                            true_iso_freq_table_15b,
+                            eqz_preset_iso_15b[i].f_amp, EQZ_ISO15_BANDS_MAX );
+
+        test_interpolation( true_vlc_freq_table_10b,
+                            eqz_preset_vlc_10b[i].f_amp, EQZ_VLC10_BANDS_MAX,
+                            true_iso_freq_table_31b,
+                            eqz_preset_iso_31b[i].f_amp, EQZ_ISO31_BANDS_MAX );
+
+    }
+}
+
+int main( void )
+{
+    log( "Testing bad interpolant parameters\n" );
+    test_bad_interpolant_param();
+
+    log( "Testing interpolation of equalizer preset values\n" );
+    test_some_interpolants();
+
+    return 0;
+}
-- 
1.9.1



More information about the vlc-devel mailing list