Arduinos simply aren’t up to the task of acquiring, storing, and processing image data in a reasonable time frame. Microcontrollers in general excel at responding to discrete events but are not designed or intended to be used with large amounts of streaming data. More powerful microcontrollers like the ARM line may have fast enough execution times to get basic functionality with a 640x480 camera but even then you are consuming a huge portion of the available bandwidth with little room to do anything else. Higher resolutions and frame rates without a JPEG output option is not feasible with your standard microcontrollers.
Non traditional microcontrollers like the XMOS and Propeller might be more up your alley for applications like this. Both controllers have multiple cores and the XMOS is capable of running at relatively high frequencies. You may be able to dedicate a core to acquiring an image while other cores are busy processing data as it becomes available. You would have to do the due diligence of researching their capabilities to see if they can meet your requirements.
The ideal solution for camera interfacing is to use programmable logic like CPLDs and FPGAs. These devices excel at working on repetitive tasks involving large amounts of high speed data making them suitable for any camera device you throw at them. They can simultaneously acquire an image, store it in external memory, compare the differences between the new and old frame, and make the data available through an SPI, I2C, or other interface of your choice. The problem with these is there is a steep learning curve to understand how they work and how you are supposed to program them. Traditional programming concepts taught to C programmers don’t apply here.
thebecwar already did a first round of go/no-go timing checks for the Arduino and says you are pushing it even running the camera at its slowest while using highly optimized assembly code. Because of the lack of experience you have in this subject matter, I would consider finding another way to tackle your project.
-Bill