A few years ago I working as an animal control officer in Central PA. I got a report of a mountain lion sighting in a housing development that was surrounded by some dense forest. I went up there with a local police officer who was an avid hunter and we found some tracks left by deer that had definatly had a scare. We also found some large paw type tracks. Neither one of us had any experience with tracking cats before, so we were clueless as to whether there had been a mountain lion there, or just a big dog. We contacted a state game warden who officially told us that there were no mountain lions in PA. Unofficially he advised us to stay out of that forest for a few days.
After that I decided to get educated on the difference between K9 and feline tracks. I think the picture in the OP is from a large dog. K9 tracks always show claw marks because dogs can't retract their claws. From what I've been told, cats only extend their claws in the ground to gain traction. When that occurs they also exert a large amount of force into the ground, ripping up chunks of dirt, and therefore leaving very poor tracks. Felines also tend to have a larger pad at the base of the paw than K9s do. You can tell the difference by drawing an X through the track. Draw a diagonal line from top left to bottom right that travels between the first and second toes on the track. Then draw a line from top right to bottom left between the third and fourth toes. If you can draw those lines so that they intersect and form and X, or very close to one, without hitting the base pad of the track you have yourself a K9. If you can't form and X you have a feline. The front two toes in a K9 track will always be even with each other, while a feline's front two toes will be offset with one slightly in front of the other.
In light of that I am pretty sure that what I saw that day was from a dog. The second picture posted of the track in the soft mud looks to be a much better candidate for a feline track. I've come across some bobcat tracks in snow and they looked similar to that, but smaller.