Fuzzy Connectedness is an important image segmentation routine for image processing of medical images. It is often used in preparation for surgery and sometimes during surgery. It is important to have an algorithm which can execute very fast, especially in the intra-operative environment. We have taken code from a popular image processing toolkit called ITK and ported it to a C environment. We optimized the implementation to give maximal performance (giving speedup of 23 times). We attempted three different levels of parallelization. We found that MPI was not an efficient method of parallelization as the algorithm is data dependant and large amounts of communication must be done. This communication overshadows the speed increase from doing computation on multiple processors, or nodes in a cluster. However, some limited speedup over the optimizations was obtained using OpenMP on an SMP system leading to a speedup of fifty using four processors over the original ITK implementation.