OCR 후에 유사한 문자열을 찾기 위해 Levenshtein 거리를 사용하고 있습니다. 그러나 일부 문자열의 경우 시각적 모양이 분명히 다르지만 편집 거리는 동일합니다.문자 유사성을 결정하는 방법은 무엇입니까?
예를 들어 문자열 Co이 일치하는 항목을 반환합니다
CY (1)
CZ (1)
Ca (1)
을 고려, 그 Co는 OCR 엔진의 결과이며, Ca는 것보다 더 가능성이 일치하는 것입니다. 따라서 Levenshtein 거리를 계산 한 후 시각적 유사성을 정렬하여 쿼리 결과를 구체화하고 싶습니다. 이 유사성을 계산하기 위해 Arial과 같은 표준 산세 리프 글꼴을 사용하고 싶습니다.
이 용도로 사용할 수있는 라이브러리가 있습니까? 아니면 어떻게 구현할 수 있습니까? 또는 Levenshtein 거리보다 더 정확한 문자열 유사 알고리즘이 있습니까? 추가적으로 사용할 수 있습니까?
을 시각적 유사성을 기반으로 '대체 비용'을 계산할 수있는 표를 찾고 난 후에 잠시 동안은 거의 성공하지 못한 채 그런 것을 찾고 있었기 때문에 새로운 문제로 살펴보기 시작했습니다. 나는 OCR과 함께 일하고 있지 않다. 그러나 문자의 확률 적 검색에서 검색 매개 변수를 제한하는 방법을 찾고있다.인간이 문자를 시각적으로 혼동했기 때문에 잘못 입력 되었기 때문에 동일한 원칙이 적용됩니다.
내 접근 방식은 8 비트 필드에서 획 성분에 따라 문자를 분류하는 것이 었습니다. 비트는 왼쪽에서 오른쪽으로되어
7: Left Vertical
6: Center Vertical
5: Right Vertical
4: Top Horizontal
3: Middle Horizontal
2: Bottom Horizontal
1: Top-left to bottom-right stroke
0: Bottom-left to top-right stroke
는 소문자 문자의 경우, 왼쪽 센더는 비트 1에 기록되며, 대각선 등의 비트 0의 우측에 센더.
이 스키마에서는 시각적 유사성에 따라 문자의 순위를 매기려고 다음 값을 사용했습니다.
m: 11110000: F0
g: 10111101: BD
S,B,G,a,e,s: 10111100: BC
R,p: 10111010: BA
q: 10111001: B9
P: 10111000: B8
Q: 10110110: B6
D,O,o: 10110100: B4
n: 10110000: B0
b,h,d: 10101100: AC
H: 10101000: A8
U,u: 10100100: A4
M,W,w: 10100011: A3
N: 10100010: A2
E: 10011100: 9C
F,f: 10011000: 98
C,c: 10010100: 94
r: 10010000: 90
L: 10000100: 84
K,k: 10000011: 83
T: 01010000: 50
t: 01001000: 48
J,j: 01000100: 44
Y: 01000011: 43
I,l,i: 01000000: 40
Z,z: 00010101: 15
A: 00001011: 0B
y: 00000101: 05
V,v,X,x: 00000011: 03
이것은 그대로, 내 목적에는 너무 원시적이며 더 많은 작업이 필요합니다. 당신은 그것을 사용할 수 있습니다, 또는 아마도 귀하의 목적에 맞게 적응할 수 있습니다. 이 계획은 매우 간단합니다. 이 순위는 모노 스페이스 글꼴입니다. sans-serif 글꼴을 사용하는 경우 값을 다시 작성해야 할 가능성이 큽니다.
이 테이블은 대소 문자를 모두 포함하는 하이브리드 테이블이지만 대소 문자 만 구분하면 소문자 만 더 효과적 일 수 있으며 특정 문자를 적용 할 수도 있습니다. 케이싱 페널티.
초기 실험입니다. 꼭 (예를 들어, 비트 시퀀싱을 변경하여) 개선 할 수있는 방법을 발견한다면 꼭 그렇게하십시오.
그래서 거리 함수에서 다른 문자 쌍을 대체하기위한 비용이 다릅니다. 오히려 하나 포함 된 문자의 두 irrepective 일련의 비용을 추가 교체보다는이다
는 - 대신 특정 특정 문자를 교체하는 비용 0.0과 2.0에 뭔가를 반환 비용 함수를 교체해야 문맥. 그림과 같이, 단지 replace_cost 기능에 대한 replace_cost 상수를 내 전체 편집 거리 구현 교환 여기
cost[x][y] = min(
cost[x-1][y] + 1, // insert
cost[x][y-1] + 1, // delete,
cost[x-1][y-1] + cost_to_replace(a[x],b[y]) // replace
);
: 다음 메모이 제이션의 각 단계에서
, 바로이 비용 함수를 호출https://codereview.stackexchange.com/questions/10130/edit-distance-between-two-strings
cost_to_replace 함수를 구현하는 측면에서 문자의 유사성을 기준으로 비용 매트릭스가 필요합니다. 테이블이 떠 다니거나 테이블의 각 쌍을 한 쌍의 이미지에 쓰고 표준 시각 기술을 사용하여 유사성을 비교하여 직접 구현할 수 있습니다.
다른 방법으로 감독 된 방법을 사용하여 여러 가지 OCR 오독을 수정하고 위 비용 테이블이 될 테이블의 발생을 기록 할 수 있습니다. (즉, OCR이 잘못되었을 때 문자가 유사해야 함).
일반적으로 나는 Damerau-Levenshtein이 단지 Levenshtein보다 훨씬 자주 사용되는 것을 보았으며 기본적으로 조 변경 작업을 추가합니다. 그것은 사람의 철자법 오류의 80 % 이상을 차지하기로되어 있으므로이를 확실히 고려해야합니다.
은 특정 문제에 관해서는, 당신은 쉽게 비 대문자와 대문자를 대체 할 때 비용을 증가하는 알고리즘을 수정할 수 있고, 그 반대가 그런 걸 얻을 : '당신이 경우
dist(Co, CY) = 2
dist(Co, CZ) = 2
dist(Co, Ca) = 1
이것은 사용중인 이미징 머신과 OCR 프로그램 자체에 따라 매우 다양 할 수 있습니다. IMHO의 가장 좋은 전략은 훈련 데이터 세트를 작성하고이 확률을 경험적으로 계산하는 것입니다. – ElKamina