Moving in unknown environments requires real-time processing of sensor information e.g. for map reconstruction and navigation. In case of stereo image processing results have to be available in time even if high computational costs occur. This paper addresses the problem of real-time image processing for motion planning and distance estimation based on stereo camera images. Ensuring hard real-time with complex algorithms on modern computer architectures is difficult to realize due to unpredictable execution times of algorithms with data dependent runtime. To solve this problem a scheduling scheme based on task pairs can be used to avoid an unpredicted state after a deadline violation. A new two level scheduler as extension of RTAI/Linux will be introduced. This new scheduling scheme allows to use AnyTime algorithms, which can provide results even if the task is not finished. A SURF algorithm used for stereo image processing was modified to match the AnyTime concept: First results are made available early and are improved over time. In case of a missed deadline the image processing task will not fail due to already provided results. Design considerations, implementation and results will be shown.