Electrocardiogram (ECG) paper records are used commonly for diagnosing heart abnormalities. The stored ECG paper records are recorded on thermal paper and may face ink evaporation problem over the time. Generally, to overcome this problem ECG paper record is scanned and stored as an image. However, the addition of noise during scanning such as low resolution scan, blurring, folding of paper, non-uniform lighting, orientation etc. can create difficulty in information retrieval. Current work robustly handles various degradation problems encountered in ECG paper scanning using modified k-fill algorithm. The proposed algorithm is tested with 836 ECG paper recordings with different types of degradations like aging effect, folding effect, ink evaporation effect, blurring effect and low resolution effect. We extracted clinically important parameters such as heart rate etc. with accuracy of 97.33% and abnormalities such as bradycardia, tachycardia, and atrial flutter from the ECG paper records using perceptual spectral centroid method. Overall accuracy of our prediction algorithm was found out to be 98.6%. We assume our work would be low cost, preliminary expert mechanism at rural places in the absence of expert cardiologist.