Another approach which I'd like to try at some point is RBS (randomized batch sampling) which would seem to be a good way to come up with a reasonably accurate estimate in early sprints.
It can be used:
Planning poker
Previous scrum projects, it would be analogous estimate
Consensus
History points
It also applies parametric estimates, for example man hours, machine hours Saving Changes...