I know that this is not an answer to you question but may be an answer to you problem. There are some cameras that have a TTL serial interface.
Such as:
There are probably others. I am still looking for a cheaper solution.
I do not know what kind of frame rate you can get out of these cameras but they will easily interface to an Arduino.
I hope this help. If not, forget I said anything.