這種粘連字元分割有什麼好的演算法?
這種粘連字元分割有什麼好的演算法？字元可能有粘連，筆畫也可能有斷裂的情況。我是圖像處理菜鳥，請大牛提供點思路。
#2016.01.28 補充編輯
根據評論中稍微嚴謹一點的描述，重新編輯了本條回答，解釋了部分疑點。
首先是盡量過切分，找出所有可能切分點。然後相當於窮舉了所有排列組合的方式（這裡會根據寬高比去除不可能出現的情況，降低計算代價），每種組合方式都會對應出一個識別結果序列。
判斷子圖是不是字元這個步驟不需要。因為很難判斷出非字元和字元（非字元的樣本根本是無窮的）。 本方法的關鍵在於深度優先搜索、過切分策略與錯誤組合的去除，就這麼理解：正確的切分點，一定包含在所有切分序列的排列組合之中，無非就是在所有切分序列的組合中找出識別置信度最大的那一種。 如果要加速或者改進，可以嘗試並行計算每種排列的識別置信度。 或者將全局的深度優先搜索找最優解這種方案替換，改用次優解的貪婪、A*等，這種改動有較高風險，需要結合具體項目看測試結果來衡量。 錯誤組合的去除方法，一般而言根據字元寬高比可以搞定絕大部分。在印刷漢字字元串中使用有較高風險（漢字有很多左右結構、左中右結構），因此當時我也做了一個配套演算法，版面分析+字元寬度、高度估計。#原始答案
哈哈哈哈哈，這是我最拿手的問題。1.水平方向外輪廓投影直方圖，聯通域分析，計算出所有可能的切分點。外輪廓投影就是從垂直方向上從上而下、從下而上，找到字元的高度。然後高斯平滑這個投影直方圖，然後找局部極值點序列，就是基於投影直方圖的切分點，聯通域分析，就是找出所有聯通域的左右邊緣，作為可能的切分點。2.根據所有的切分點，求取所有可能的組合。意思就是，舉例說吧，假設切分點序列是ABCD，那麼由切分點組成的切分字元段的組合就是AB"BC"CD，AC"CD，AD，AB"BD這麼四種情況，我當時是直接將切分點組成一個上三角矩陣，行列分別是所有的順序切分點。3.你需要訓練一個字元識別引擎，比如SVM，依次把所有的可能切的切分字元段放進去識別，得到識別結果與置信度（一般libSVM輸出的是距離，你需要計算一個近似置信度）然後，在步驟2中的矩陣依次填充所有的置信度數值，然後深度優先搜索，找到最大置信度數值的路徑，即當前的最優切分結果。如果有必要，繼續搜索，將潛在可能次優的輸出結果一併輸出。
4.可選步驟，你可以通過預設字元高寬，再篩一遍步驟3中所有不可能的切分段（比如單個字元過寬或者過窄）。5.可選步驟，如果你的字元串，有實際意義或者某種校驗方法，可以繼續再篩一次步驟3的識別結果。例如識別的是身份證號，可以計算最後一位是不是前面所有數字的校驗碼。類似的後處理方法能夠有效短時間提升系統性能。總的來說，思路就是先把所有可能的切分點序列的組合找到找全，然後再根據手頭先驗知識把最優結果找到。
祝順利。
補充編輯
這個方法不需要像水滴法大量的演算法規則，也不像普通投影極值切分法那樣容易錯切，純粹是我本人在上一家公司里開發的文本行演算法，印刷體漢字也有效。如果一定要起個名字，我希望就叫它，NicolARun暴力無腦切分法。*寫論文的話記得添加引用和參考文獻噢
*商業用途的話，記得在頭文件里cite:NicolARun，授權你一切商業用途手機碼字，格式抱歉
同意@NicolARun的答案，和手寫識別中的策略類似，可以過切分加動態規劃，比較經典的解法。看到你這個例子，感覺字元粘連不算嚴重，按縱向穿越量應該能切到不錯的精度，再加上字元較為一致的寬度，應該可以調到想要的精度。
可以看出寬度大約是在一定範圍內的，最簡單的方法是可以先用字元寬度判斷是否連在一起，然後利用一定寬度和腐蝕判斷出連續字元的分割點的坐標粗範圍，之後可以使用垂直投影法設定一個白像素閾值分割。雖然簡單粗暴，但是應該有點用吧。
可以利用寬度的中位數值：
def median_split_ranges(peek_ranges):
new_peek_ranges = []
widthes = []
for peek_range in peek_ranges:
w = peek_range[1] - peek_range[0] + 1
widthes.append(w)
widthes = np.asarray(widthes)
median_w = np.median(widthes)
for i, peek_range in enumerate(peek_ranges):
num_char = int(round(widthes[i]/median_w, 0))
if num_char &> 1:
char_w = float(widthes[i] / num_char)
for i in range(num_char):
start_point = peek_range[0] + int(i * char_w)
end_point = peek_range[0] + int((i + 1) * char_w)
new_peek_ranges.append((start_point, end_point))
else:
new_peek_ranges.append(peek_range)
return new_peek_ranges
下圖是最終的結果，「本上就」被切割開了。
正好最近處理驗證碼，試了滴水演算法效果挺不錯。由於我的驗證碼中只有小部分字元會粘連，所以沒有對全圖實施滴水分割，僅提取出粘連的兩個字元後再滴水。代碼可參考：GitHub - lan2720/fuck-captcha: Machine Learning 2016 final project稍微改動下就可以對整張圖都用滴水演算法切分了
曾經做過驗證碼粘連圖像的分割，多種思路結合的方法比較靠譜，首先要得到足夠的先驗信息（比如字元寬度，筆畫寬度），然後根據這些信息進行垂直投影和筆畫寬度分析，切割開一部分粘連字元，最後對一些沒有切開的粘連字元使用聚類的方法強制切割。缺點是聚類切分準確率不會100%，可能造成一些字元部件缺失，但是應該能解決大部分問題了。
滑動窗口+模板匹配分割
不需要分割，直接用LSTM+CTC識別
0 同意 @NicolARun
1 使用deep learnning進行字元分類
2 使用RBF網路計算置信度，同時拒絕非字元3 使用維特比演算法找最短路徑可以試試遞歸神經網路
這個看上去還挺容易的，有一個叫做基於慣性的大水滴滴水法，可以切割這種粘連字元。沒有粘連的那些就用連通域分割法，類似基於密度的聚類。
字母寬度差不多的話用滑動窗口分割
曾經做過手寫數字分割，綜合字元寬度、中心，蓄水池，滴水（改進）等一些特徵和方法
推薦閱讀：