I don't think there's a good solution to this problem without incorporating some kind of prior distribution, and a statistical model of what paws tend to look like. Heuristics will only take you so far.

edit: come to think of it, something like mean-shift or ICP would probably do very well on this.