In this paper, we present a new, script-independent, HMM-based technique to locate text lines on images containing one or more paragraphs of single-column text. The parameters of the HMMs are trained on-line on each image using an unsupervised training procedure. We present results of line finding experiments in Arabic, Chinese and English to demonstrate the performance as well as the script-independent nature of the technique. Comparison of HMM-based line finding with manual line finding shows that the use of HMM-based technique does not lead to a significant increase in the recognition error rate.