Esse problema é tipico de um OCR. Conhecido como segmentação de caracteres (char segmentation algorithms
, se você procurar no google), esse problema é estudado desde os anos 50.
No geral, o algoritmo que tanto o tesseract e o ocropus usam (os 2 mais conhecidos OCRs opensources) faz o seguinte:
Encontra os componentes conectados - Varre a imagem e encontra todos os pixels que tem vizinhos. Assim os caracteres que não grudam entre si podem ser facilmente separados.
Para cada componente conectado, calcula uma caixa que enquadra todos os pixels do componente (bounding box).
Só que, como você citou, esse algoritmo falha em 2 casos. Quando os caracteres grudam e quando um carácter se quebra em 2.
Para resolver esse problema, os ocrs usam uma técnica chamada Seam Carving. Em termos gerais, é um algoritmo que calcula um caminho que gaste menos "energia", ou passe por menos obstáculos. No caso da segmentação de caracteres, um caminho com menos obstaculos é um caminho vertical que menos encoste no contorno do caracter.
Por exemplo, imaginemos que temos a seguinte imagem:
Os caminhos com menos obstáculos são os seguintes:
Nessa imagem, os possíveis cortes estão em preto na frase e na parte de baixo um gráfico mostrando a quantidade de obstáculos calculado pelo algoritmo para cada coluna de pixels.
O resultado desse algoritmo não são os cortes em si, mas sim as possibilidades de corte. Alguns estão certos e outros não. A próxima etapa do OCR se propõe a resolver esse problema.
Nessa etapa, o OCR gera varias possibilidades de recorte, juntando ou separando os segmentos encontrados, como na imagem abaixo:
Isso gera dezenas de possibilidades para o OCR. Mas como o OCR sabe qual é o recorte correto? Simples, ele joga cada possibilidade em um reconhecedor de caracteres, que vai retornar um grau de confiança daquele recorte ser uma letra.
O OCR então pega todos os recortes no qual a soma dos graus de confiança seja a maior possível.
PS: Eu não vou detalhar cada algoritmo aqui, porque daria um post de 5 mil palavras, mas você pode estudar todos esses algoritmos implementados no OCRopus.