Growing needs for surveillance in locations without power lines necessitates the development of a surveillance camera with extremely low-power consumption and an assured stable operation until the time of expected run-out of available energy. This paper proposes an algorithm for scheduling of video encoding configurations in a battery-operated surveillance system to reduce the image distortion while assuring the sustained operation until the battery recharge/exchange. The optimal video encoding configuration is determined based on the amount of estimated remaining event duration (considering the uncertainty of events) and remaining battery charge (considering the rate-capacity and recovery effect). The proposed algorithm consists of two steps: design-time step and run-time step. In the design-time step, prediction of remaining event duration, called duration prediction, is performed considering the uncertainty of events and tradeoff between encoding power and image quality. During run-time, video encoding configuration is switched between intra-frame encoding and inter-frame encoding based on the duration prediction obtained in design-time step and the remaining battery charge measured in run-time step. Compared to the conventional method based on the most conservative duration prediction , experimental results show that the proposed method provides 2.24 similar to 3.78 dB improvement in the image quality (in terms of peak signal-to-noise ratio in the H.264 encoding of four video sequences while satisfying the battery constraint.