diff --git a/libavcodec/a64multienc.c b/libavcodec/a64multienc.c
index 9ee0b07463..71a620b4ff 100644
--- a/libavcodec/a64multienc.c
+++ b/libavcodec/a64multienc.c
@@ -43,6 +43,7 @@
 
 typedef struct A64Context {
     /* variables for multicolor modes */
+    struct ELBGContext *elbg;
     AVLFG randctx;
     int mc_lifetime;
     int mc_use_5col;
@@ -195,6 +196,9 @@ static void render_charset(AVCodecContext *avctx, uint8_t *charset,
 static av_cold int a64multi_close_encoder(AVCodecContext *avctx)
 {
     A64Context *c = avctx->priv_data;
+
+    avpriv_elbg_free(&c->elbg);
+
     av_freep(&c->mc_meta_charset);
     av_freep(&c->mc_best_cb);
     av_freep(&c->mc_charmap);
@@ -333,8 +337,8 @@ static int a64multi_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
             buf = pkt->data;
 
             /* calc optimal new charset + charmaps */
-            ret = avpriv_do_elbg(meta, 32, 1000 * c->mc_lifetime, best_cb,
-                             CHARSET_CHARS, 50, charmap, &c->randctx);
+            ret = avpriv_elbg_do(&c->elbg, meta, 32, 1000 * c->mc_lifetime,
+                                 best_cb, CHARSET_CHARS, 50, charmap, &c->randctx);
             if (ret < 0)
                 return ret;
 
diff --git a/libavcodec/cinepakenc.c b/libavcodec/cinepakenc.c
index 8e8b73ce1d..2984b93de3 100644
--- a/libavcodec/cinepakenc.c
+++ b/libavcodec/cinepakenc.c
@@ -127,6 +127,7 @@ typedef struct CinepakEncContext {
     int min_min_strips;
     int max_max_strips;
     int strip_number_delta_range;
+    struct ELBGContext *elbg;
 } CinepakEncContext;
 
 #define OFFSET(x) offsetof(CinepakEncContext, x)
@@ -761,7 +762,8 @@ static int quantize(CinepakEncContext *s, int h, uint8_t *data[4],
     if (i < size)
         size = i;
 
-    avpriv_do_elbg(s->codebook_input, entry_size, i, codebook, size, 1, s->codebook_closest, &s->randctx);
+    avpriv_elbg_do(&s->elbg, s->codebook_input, entry_size, i, codebook,
+                   size, 1, s->codebook_closest, &s->randctx);
 
     // set up vq_data, which contains a single MB
     vq_data[0]     = vq_pict_buf;
@@ -1161,6 +1163,7 @@ static av_cold int cinepak_encode_end(AVCodecContext *avctx)
     CinepakEncContext *s = avctx->priv_data;
     int x;
 
+    avpriv_elbg_free(&s->elbg);
     av_frame_free(&s->last_frame);
     av_frame_free(&s->best_frame);
     av_frame_free(&s->scratch_frame);
diff --git a/libavcodec/elbg.c b/libavcodec/elbg.c
index ac5c53161d..9eac802688 100644
--- a/libavcodec/elbg.c
+++ b/libavcodec/elbg.c
@@ -466,12 +466,17 @@ static int init_elbg(int *points, int dim, int numpoints, int *codebook,
     return ret;
 }
 
-int avpriv_do_elbg(int *points, int dim, int numpoints,
+int avpriv_elbg_do(ELBGContext **elbgp, int *points, int dim, int numpoints,
                    int *codebook, int num_cb, int max_steps,
                    int *closest_cb, AVLFG *rand_state)
 {
+    ELBGContext *const elbg = *elbgp ? *elbgp : av_mallocz(sizeof(*elbg));
     int ret;
 
+    if (!elbg)
+        return AVERROR(ENOMEM);
+    *elbgp = elbg;
+
     ret = init_elbg(points, dim, numpoints, codebook,
                     num_cb, max_steps, closest_cb, rand_state);
     if (ret < 0)
@@ -479,3 +484,8 @@ int avpriv_do_elbg(int *points, int dim, int numpoints,
     return do_elbg (points, dim, numpoints, codebook,
                     num_cb, max_steps, closest_cb, rand_state);
 }
+
+av_cold void avpriv_elbg_free(ELBGContext **elbgp)
+{
+    av_freep(elbgp);
+}
diff --git a/libavcodec/elbg.h b/libavcodec/elbg.h
index a9a19aa5e4..abeeb4ff44 100644
--- a/libavcodec/elbg.h
+++ b/libavcodec/elbg.h
@@ -23,11 +23,16 @@
 
 #include "libavutil/lfg.h"
 
+struct ELBGContext;
+
 /**
  * Implementation of the Enhanced LBG Algorithm
  * Based on the paper "Neural Networks 14:1219-1237" that can be found in
  * http://citeseer.ist.psu.edu/patan01enhanced.html .
  *
+ * @param ctx  A pointer to a pointer to an already allocated ELBGContext
+ *             or a pointer to NULL. In the latter case, this function
+ *             will allocate an ELBGContext and put a pointer to it in `*ctx`.
  * @param points Input points.
  * @param dim Dimension of the points.
  * @param numpoints Num of points in **points.
@@ -38,8 +43,13 @@
  * @param rand_state A random number generator state. Should be already initialized by av_lfg_init().
  * @return < 0 in case of error, 0 otherwise
  */
-int avpriv_do_elbg(int *points, int dim, int numpoints, int *codebook,
-                   int num_cb, int num_steps, int *closest_cb,
-               AVLFG *rand_state);
+int avpriv_elbg_do(struct ELBGContext **ctx, int *points, int dim,
+                   int numpoints, int *codebook, int num_cb, int num_steps,
+                   int *closest_cb, AVLFG *rand_state);
+
+/**
+ * Free an ELBGContext and reset the pointer to it.
+ */
+void avpriv_elbg_free(struct ELBGContext **ctx);
 
 #endif /* AVCODEC_ELBG_H */
diff --git a/libavcodec/msvideo1enc.c b/libavcodec/msvideo1enc.c
index fa65a2fbc4..d43013ba5f 100644
--- a/libavcodec/msvideo1enc.c
+++ b/libavcodec/msvideo1enc.c
@@ -36,6 +36,7 @@
  */
 typedef struct Msvideo1EncContext {
     AVCodecContext *avctx;
+    struct ELBGContext *elbg;
     AVLFG rnd;
     uint8_t *prev;
 
@@ -117,7 +118,8 @@ static int encode_frame(AVCodecContext *avctx, AVPacket *pkt,
             }
             // try to find optimal value to fill whole 4x4 block
             score = 0;
-            avpriv_do_elbg  (c->block, 3, 16, c->avg, 1, 1, c->output, &c->rnd);
+            avpriv_elbg_do(&c->elbg, c->block, 3, 16, c->avg,
+                           1, 1, c->output, &c->rnd);
             if(c->avg[0] == 1) // red component = 1 will be written as skip code
                 c->avg[0] = 0;
             for(j = 0; j < 4; j++){
@@ -136,7 +138,8 @@ static int encode_frame(AVCodecContext *avctx, AVPacket *pkt,
             }
             // search for optimal filling of 2-color block
             score = 0;
-            avpriv_do_elbg  (c->block, 3, 16, c->codebook, 2, 1, c->output, &c->rnd);
+            avpriv_elbg_do(&c->elbg, c->block, 3, 16, c->codebook,
+                           2, 1, c->output, &c->rnd);
             // last output value should be always 1, swap codebooks if needed
             if(!c->output[15]){
                 for(i = 0; i < 3; i++)
@@ -161,7 +164,9 @@ static int encode_frame(AVCodecContext *avctx, AVPacket *pkt,
             // search for optimal filling of 2-color 2x2 subblocks
             score = 0;
             for(i = 0; i < 4; i++){
-                avpriv_do_elbg  (c->block2 + i*4*3, 3, 4, c->codebook2 + i*2*3, 2, 1, c->output2 + i*4, &c->rnd);
+                avpriv_elbg_do(&c->elbg, c->block2 + i * 4 * 3, 3, 4,
+                               c->codebook2 + i * 2 * 3, 2, 1,
+                               c->output2 + i*4, &c->rnd);
             }
             // last value should be always 1, swap codebooks if needed
             if(!c->output2[15]){
@@ -286,6 +291,7 @@ static av_cold int encode_end(AVCodecContext *avctx)
     Msvideo1EncContext * const c = avctx->priv_data;
 
     av_freep(&c->prev);
+    avpriv_elbg_free(&c->elbg);
 
     return 0;
 }
diff --git a/libavcodec/roqvideoenc.c b/libavcodec/roqvideoenc.c
index 167e6bc806..316adac45e 100644
--- a/libavcodec/roqvideoenc.c
+++ b/libavcodec/roqvideoenc.c
@@ -133,6 +133,7 @@ typedef struct CelEvaluation {
 
 typedef struct RoqEncContext {
     RoqContext common;
+    struct ELBGContext *elbg;
     AVLFG randctx;
     uint64_t lambda;
 
@@ -824,8 +825,8 @@ static int generate_codebook(RoqEncContext *enc,
     int *codebook = enc->tmp_codebook_buf;
     int *closest_cb = enc->closest_cb;
 
-    ret = avpriv_do_elbg(points, 6 * c_size, inputCount, codebook,
-                     cbsize, 1, closest_cb, &enc->randctx);
+    ret = avpriv_elbg_do(&enc->elbg, points, 6 * c_size, inputCount, codebook,
+                         cbsize, 1, closest_cb, &enc->randctx);
     if (ret < 0)
         return ret;
 
@@ -961,6 +962,8 @@ static av_cold int roq_encode_end(AVCodecContext *avctx)
     av_freep(&enc->this_motion8);
     av_freep(&enc->last_motion8);
 
+    avpriv_elbg_free(&enc->elbg);
+
     return 0;
 }
 
diff --git a/libavfilter/vf_elbg.c b/libavfilter/vf_elbg.c
index 79797ee25f..2c9c861d02 100644
--- a/libavfilter/vf_elbg.c
+++ b/libavfilter/vf_elbg.c
@@ -35,6 +35,7 @@
 
 typedef struct ELBGFilterContext {
     const AVClass *class;
+    struct ELBGContext *ctx;
     AVLFG lfg;
     int64_t lfg_seed;
     int max_steps_nb;
@@ -163,7 +164,7 @@ static int filter_frame(AVFilterLink *inlink, AVFrame *frame)
     }
 
     /* compute the codebook */
-    avpriv_do_elbg(elbg->codeword, NB_COMPONENTS, elbg->codeword_length,
+    avpriv_elbg_do(&elbg->ctx, elbg->codeword, NB_COMPONENTS, elbg->codeword_length,
                    elbg->codebook, elbg->codebook_length, elbg->max_steps_nb,
                    elbg->codeword_closest_codebook_idxs, &elbg->lfg);
 
@@ -223,6 +224,8 @@ static av_cold void uninit(AVFilterContext *ctx)
 {
     ELBGFilterContext *const elbg = ctx->priv;
 
+    avpriv_elbg_free(&elbg->ctx);
+
     av_freep(&elbg->codebook);
     av_freep(&elbg->codeword);
     av_freep(&elbg->codeword_closest_codebook_idxs);
