1. A method for estimating a pitch frequency of a speech signal, comprising: determining a line spectrum of a frame of a speech signal, the spectrum comprising a plurality of spectral lines having respective line amplitudes and line frequencies; selecting a predefined number of said spectral lines having the highest amplitudes among said spectral lines, wherein the number of selected spectral lines is less then the total number of said plurality of spectral lines; calculating a preliminary utility function over a pitch frequency range, thereby providing a preliminary utility function value for each pitch frequency in said range that is a measure of a compatibility of said selected spectral lines with said pitch frequency; identifying a predefined number of preliminary pitch frequency candidates at least partly responsive to said preliminary utility function, wherein each preliminary pitch frequency candidate is a local maximum of said preliminary utility function; calculating a final utility score for each of said preliminary pitch frequency candidates; and selecting any of said plurality of preliminary pitch frequency candidates to be an estimated pitch frequency of said speech signal at least partly responsive to any of said final utility scores.