Какое решение подойдет для фонового вычисления на php?
С минимальными затратами, с учетом Вашего сценария:
Когда пользователь нажимает кнопку - отправляем ajax запрос к скрипту который занимается генерацией картинки и делаем переход на новую страницу не дожидаясь ответа. Далее все как вы расписали.Upd
Более абстрактное и устойчивое к нагрузкам решение: очередь на стороне сервера и постоянно запущенные воркеры получающие оттуда задачи. Для очередей можно на небольших нагрузках использовать mysql, можно Redis, а можно использовать решение специально предназначенное для организации очередей - RabbitMQ.
Немного не так должно пойти. JS на странице ввода данных стартует этот фоновый запрос, показывая счетчик выполнения. При получении итвета об выполнении переводит на страницу с готовым результатом. Пример можно просмотреть на любом файловом шаринге.
Сам фоновый процесс можно организовать следуюшим образом: php скрипт создает в определенной папке текстовый файл с именем сессии полъзователя. Внутри - путь до ишодной картинки. В кроне проверяется  в этой папке наличие файлов, если файл найден, то берется и запускается обработка. по окончании обработки создается файл с именем сессии в другой папке с содержимым в виде пути к обработанному файлу.  php-скрипт, проверяющий по ajax-запросу браузера готовност просто ищет в этой папке файл с именем, как сессия и если находит, то сообсшает, что выполнено.