An optimum representative-frames (r-frames) selection method using step-wise function approximation has been developed to provide automatic indexing for a video-query-agent (VQA) system. It uses dynamic programming to simultaneously select the r-frames and corresponding segment boundaries. Experiments showed that the approximation error of the selected r-frames was less than that of two conventional methods. Retrieval experiments using a feature-based image-search engine showed that the proposed method is more robust and effective than the two conventional methods. The proposed method was implemented in a VQA system and processing time was evaluated. The results showed that the processing time for indexing was shorter than that of the conventional method.