Eles estão localizados em /usr/include/x86_64-linux-gnu/libavcodec
. Um simples sudo find / -name "libavcodec"
teria revelado isso.
Os pacotes que eu instalei são:
libavutil-dev:amd64 7:2.8.6-1ubuntu2
libswresample-dev:amd64 7:2.8.6-1ubuntu2
libavcodec-dev:amd64 7:2.8.6-1ubuntu2
libavformat-dev:amd64 7:2.8.6-1ubuntu2