Давайте сделаем big.gif
:
convert -size 1600x1600 xc:yellow -fill black -draw "rectangle 5,130 14,139" big.gif
и small.gif
convert -size 10x10 xc:black small.gif

Теперь давайте посмотрим на обрезанной области поиска:
convert big.gif -crop 50x500+0+118 x.gif

Таким образом, команда, которую вы должны были бы быть:
convert big.gif -crop 50x500+0+118 +repage miff:- | compare -metric mse -subimage-search miff:- small.gif null:
0 (0) @ 5,12
Это приносит время поиска вниз от 91 секунд до 0,7 секунды.
Если реальная проблема сложнее, или больше, или более насущной, вы можете разделить изображение на две части и сделать две половинки параллельно - помните, чтобы перекрывать половинки по размеру вашего испрашивается вспомогательного изображения:
convert big.gif -crop 50x260+0+118 +repage miff:- | compare -metric mse -subimage-search miff:- small.gif null: &
convert big.gif -crop 50x260+0+368 +repage miff:- | compare -metric mse -subimage-search miff:- small.gif null: &
wait
Теперь это занимает 0,4 секунды :-)