Recently, a character segmentation method based on graph cuts has been introduced. In this report, we extend this method to multi-label graph cuts. Instead of sequential segmentation of single characters from a text line, all characters are segmented at once. The method is especially suitable for applications where subsequent images contain the same (known) number of characters. This prior knowledge and the approximate positions of characters relative to the defined text region are included in the formulation of the energy functional. This approach provides significant segmentation quality improvement, in particular, when characters are touching, which may happen , e.g. due to poor print quality or scratches on the material's surface. To illustrate the performance changes, we compare the results obtained with this and previously known methods, based on real data.