After talking with some friends, basically I could get this to be a lot faster if I just wrote it in Cython. (the skimage.transform.seam_carve function is written in Cython). Also, I realize now that the double for loop in Cython is actually fast, so that means that the skimage implementation of dynamic programming is optimal. But I can still change it to accept the accumulated energy matrix!