Scratch

I'm making a scrolling game that has a first-person perspective (the background moves left or right depending on where you look).
In this game, there are other characters who walk from left to right across the screen.
I know how to make them walk across the screen, and I know how to make them scroll along with the background as you look around (if they are standing still, of course). What I DON'T know how to do is to make it so that they walk from point A to point B at the same "speed" even while you look around.

For example, let the other character's walking speed be 5. If you aren't looking around, their walking speed will be 5, and their x position on the screen will also be changing by 5.
If you are following them with your eyes, their walking speed will still be five, but their x position on-screen will not change since you are following them.
If you are scanning to the left (behind the other character), their walking speed will still remain at 5, but their x position on-screen will be changing by more than 5.
If you are scanning to the right (in front of the other character), their walking speed will, again, remain at 5, but their position on-screen will be shifting to the left since you are scanning ahead of them.

It's a problem of perspective, and it has me stumped. Please help.