How to make Okular play embedded video

So I create presentations using LaTeX and the Beamer class. This allows me to embed videos (.mp4, .avi, .gif) formats in my presentation. These seem to play well in full versions of acrobat reader but these videos DO NOT play in Okular.

Is there something else I should do to configure Okular? Is this a LaTeX question or a Ubuntu question? ;)

Code snippet to embed video in latex

\documentclass[bookmarks=true]{beamer}
\setbeamertemplate{footline}[page number]
\setbeamercolor{structure}{bg=yellow, fg=black}
\usepackage{times}
\usepackage[T1]{fontenc}

\usepackage{movie15}
\usepackage{fourier-orns}

\begin{document}
    \begin{frame}
    \frametitle{Slide Title Here}

    \centering
    \includemovie{6.5cm}{6.5cm}{./figures/Video.avi}

    \end{frame}
\end{document}

The following worked for me:

1. Change the backend of Phonon (which is used by Okular to play videos) to the VLC one. For me it sufficed to install the respective package:

   sudo apt install phonon-backend-vlc
   

   On newer versions of Ubuntu, the crucial package is phonon4qt5-backend-vlc.

2. Use multimedia instead of movie15:

   \documentclass{beamer}
   \usepackage{multimedia}
   
   \begin{document}
       \begin{frame}
           \movie[poster, height=6.5cm, width=6.5cm]{}{/figures/Video.avi}
       \end{frame}
   \end{document}
   

Movie15 is actually absolete now. You'd better use media9, however chances are this also won't work since a lot of pdf-readers just won't play video's for security reasons.