Isso funciona:
sudo apt-get install imagemagick libmagickcore-dev libmagickwand-dev
de acordo com o comentário de dalibor-filus abaixo.
[ Resposta original - Ok, parece que resolvi isso com apt-get install imagemagick libmagickwand-dev
, então libmagick9-dev não foi necessário. ]