Best Sensor for tracking motion
Your problem is made a little bit more difficult by your selection of a surface that reflects neither IR nor ultrasound well.

Accelerometers are almost totally useless for position feedback.

We could really do with some more information about your setup - it looks like you've tried to abstract away the details to make it simpler to answer, but background information is often helpful.

Possible solutions include:


A camera above your "object" tracking it with OpenCV or similar. (Unclear on whether this is feasible)
If there is a wall behind your object which is not black and soft, measure the distance from this wall instead
If your "object" has USB support then an optical mouse dragged over the ground will give you fairly accurate odometry
If your object is on wheels, put an encoder on the wheels to measure their rotation
A pattern of alternating black/white stripes on the floor which can be measured with a pair of photosensors (one in front of the other, closer spaced than the stripe width) to determine movement


Which solution is best for you depends on the specifics of your project.