  Practical image segmentation tasks concern images which must be reconstructed
from noisy, distorted, and/or incomplete observations. A recent approach for
solving such tasks is to perform this reconstruction jointly with the
segmentation, using each to guide the other. However, this work has so far
employed relatively simple segmentation methods, such as the Chan--Vese
algorithm. In this paper, we present a method for joint
reconstruction-segmentation using graph-based segmentation methods, which have
been seeing increasing recent interest. Complications arise due to the large
size of the matrices involved, and we show how these complications can be
managed. We then analyse the convergence properties of our scheme. Finally, we
apply this scheme to distorted versions of ``two cows'' images familiar from
previous graph-based segmentation literature, first to a highly noised version
and second to a blurred version, achieving highly accurate segmentations in
both cases. We compare these results to those obtained by sequential
reconstruction-segmentation approaches, finding that our method competes with,
or even outperforms, those approaches in terms of reconstruction and
segmentation accuracy.
