In this paper, two novel approaches, gradient-based and direct strain estimation techniques, are proposed for high-quality average strain imaging incorporating a cost function maximization. Stiffness typically is a continuous function. Consequently, stiffness of proximal tissues is very close to that of the tissue corresponding to a given data window. Hence, a cost function is defined from exponentially weighted neighboring pre- and post-compression RF echo normalized cross-correlation peaks in the lateral (for displacement estimation) or in both the axial and the lateral (for direct strain estimation) directions. This enforces a controlled continuity in displacement/strain and average displacement/strain is calculated from the corresponding maximized cost function. Axial stress causes lateral shift in the tissue. Therefore, a 1-D post-compression echo segment is selected by incorporating Poisson's ratio. Two stretching factors are considered simultaneously in gradient-based strain estimation that allow imaging the lesions properly. The proposed time-domain gradient-based and direct-strain-estimation-based algorithms demonstrate significantly better performance in terms of elastographic signal-to-noise ratio (SNRe), elastographic contrast-to-noise ratio (CNRe), peak signal-to-noise ratio (PSNR), and mean structural similarity (MSSIM) than the other reported time-domain gradient-based and direct-strain-estimation techniques in finite element modeling (FEM) simulation and phantom experiments. For example, in FEM simulation, it has been found that the proposed direct strain estimation method can improve up to approximately 2.49 to 8.71, 2.2 to 6.63, 1.5 to 5, and 1.59 to 2.45 dB in the SNRe, CNRe, PSNR, and MSSIM compared with the traditional direct strain estimation method, respectively, and the proposed gradient-based algorithm demonstrates 2.99 to 16.26, 18.74 to 23.88, 3 to 9.5, and 0.6 to 5.36 dB improvement in the SNRe, CNRe, PSNR, and MSSIM, respectively, compared with a recently reported time-domain gradient-based technique. The range of improvement as noted above is for low to high applied strains. In addition, the comparative results using the in vivo breast data (including malignant or benign masses) also show that the lesion size is better defined by the proposed gradient-based average strain estimation technique.