Se me ocurre una idea pero la tendria q programar para ver que tal anda...

*Conocer que pixels pertenecen a cada provincia es facil, se hace haciendo un BFS sobre la imagen y voy numerando cada provincia.

*Despues elegiria una cantidad de puntos al azar distintos para cada provincia... ( mientras mas mejor ).

*Y veria si trazando una recta  desde los puntos de una provincia, llamemosla P1, hacia todos los puntos de otra provincia P2.

*2 provincias son adyacentes si existe una linea negra en una recta que separe puntos de P1 con puntos de P2, sino es asi, existe alguna provincia entre medio de estas, por la recta que estoy tomando.

Igual no es un metodo exacto, habria q probarlo a ver si es bueno o no.

Pienso al igual que tú, creo que la cosa es ir siguen las lineas rectas, de alguna manera considerar un anchura y relacionar la región que hay a la izquierda del pixel más a la izquierda, y a la derecha del pixel más a la derecha. El problema está, como bien dices cuando hay bifurcaciones en las regiones. Aun no lo tengo claro, pero quizá hubiese alguna manera de "detectar" esa situación...¿?