The 4 times is actually quite good. The problem is that you are running a resource extensive image processing algorithm on a smartphone. We already used an quite simple algorithm but it was still the bottleneck. With the newest smartphones that have more capabilities the result gets better. Real-time image processing on a smartphone or a similar device is a quite new research area, so better results can be expected in the future. We are already looking at possible improvements to this part of the prototype. Besides improving the tracking algorithm itself, it might also be an option of trying to predict how a user is going to move. We have also some other ideas, this was our first prototype.
I should also point out that if you test the prototype it does feel better then you might think. One reason for this is that you are walking around while not seeing the real world, so you walk quite carefully.