Mandible bone segmentation from computed tomography (CT) scans is challenging due to mandible's structural irregularities, complex shape patterns, and lack of contrast in joints. Furthermore, connections of teeth to mandible and mandible to remaining parts of the skull make it extremely difficult to identify mandible boundary automatically. This study addresses these challenges by proposing a novel framework where we define the segmentation as two complementary tasks: recognition and delineation. For recognition, we use random forest regression to localize mandible in 3D. For delineation, we propose to use 3D gradient-based fuzzy connectedness (FC) image segmentation algorithm, operating on the recognized mandible sub-volume. Despite heavy CT artifacts and dental fillings, consisting half of the CT image data in our experiments, we have achieved highly accurate detection and delineation results. Specifically, detection accuracy more than 96% (measured by union of intersection (UoI)), the delineation accuracy of 91% (measured by dice similarity coefficient), and less than 1 mm in shape mismatch (Hausdorff Distance) were found.