Computer-aided diagnosis (CAD) systems must show sufficient versatility to produce robust analysis on a large variety of data. In the case of colonography, CAD has not been designed to cope with the presence of stool, although labeling the stool with high contrast agents replaces the use of laxatives and reduces the patient discomfort. This procedure introduces additional challenges for the diagnosis, such as poorly tagged stool, stool sticking to colonic walls, and heterogeneous stool (tagged stool mixed with air or untagged stool). Our study proposes a robust algorithm for heterogeneous stool removal to be employed as a preprocessing module for CAD systems in colonic cancer detection. Colonoscopy data are automatically cleansed of residual stool to enhance the polyp appearance for improved diagnosis. The algorithm uses expectation-maximization, quadratic regression, level sets and minimum variance. Results show stool removal accuracy on polyps which are partially or fully covered by stool. The results are robust on stool lining and large pools of heterogeneous and weakly-tagged stool. The automatic detection of colon polyps using our CAD system on cathartic-free data improves considerably with the addition of the automatic stool removal module from 74% to 86% true positive (TP) rate at 6.4 false positives (FP)/case.