PDF에서 텍스트를 추출하는 알고리즘 (뒤죽박죽으로 재 배열 된 텍스트 레이아웃)

Question

PDF는 많은 개별 텍스트 개체로 구성됩니다. 종종 이러한 객체는 문서에 나타나는 순서대로 배치되므로 문서 텍스트를 추출하는 작업은 PDF 스트림에 나타나는 순서대로 텍스트 객체를 읽는 것만 큼 간단합니다.

그러나 많은 PDF가 좋지 않습니다.

PDF 사양에서는 텍스트를 PDF 스트림 내에서 정렬 할 필요가 없습니다. PDF의 끝 부분이 스트림의 시작 부분에 있고 중간 부분이 끝나고 시작 부분이 중간에있는 PDF를 보는 것은 드문 일이 아닙니다. 극단적 인 경우 스트림은 순서가없는 텍스트 상자의 뒤범벅입니다.

PDF 스트림에서 개체의 적절한 텍스트 흐름을 결정하기위한 알고리즘은 무엇입니까?

간단한 문서의 경우 텍스트 순서를 지정하는 것이 너무 어렵지 않습니다. 개체를 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 정렬 한 다음 맨 아래 왼쪽 텍스트 상자에서 텍스트를 추출하여 아래로 작업하십시오. 그러나 문서에는 종종 여러 열, 제목, 부제목, 머리글, 바닥 글, 탭 단락 등이 있습니다. 여러 가지 상황에서 견고한 솔루션이 있습니까?

명확성을 위해 다음은 구현하려고하는 함수 프로토 타입의 예입니다.

def sort_according_to_text_flow(objs, page_width, page_height): 
    # objs    A list of objects where each object is a dict containing: 
    #  x, y   The top-left corner position of the text box 
    #  width, height The width and height of the text box 
    #  text   A string of the text 
    # page_width/height Width/height of the page 
    # returns the list of objects, ordered for natural reading 

잠시 동안 왼쪽에서 오른쪽 방향 언어 만 처리한다고 가정 해 봅시다.

Answer 1

이 문제는 대개 "top down document layout analysis (톱 다운 문서 레이아웃 분석)"라고하는 꽤 많은 연구 주제 인 것으로 보입니다. 하나 research paper summarizes 적지 다른 알고리즘 :

전형적인 하향식 방법은 수평 및 수직 투영 정보를 이용 작은 영역으로 문서 화상을 분할함으로써 진행할. X-Y Cut 알고리즘 [13]은 투영 프로파일의 계곡을 기반으로 문서 이미지를 섹션으로 나누기 시작합니다 (그림 7 참조). 알고리즘은 현재가로 및 가로 축에 현재 세그멘테이션의 영역을 교대로 교대로 반복하여 문서를 분할합니다. 영역의 원 자성을 결정하는 특정 기준이 충족 될 때 분할이 중지됩니다. 프로젝션 프로파일 기반 기술은 문서의 기울기에 매우 민감합니다. 소량의 비뚤어 짐 (skew)은 영사법의 성질을 완전히 바꿀 수 있었고 결과적으로 맑은 골짜기가 발생하지 않았습니다. 따라서 문서를 스캔하는 동안 극단적 인주의를 기울여 을 찍거나 조각화 프로세스를 수행하기 전에 신뢰할 수있는 기울이기 보정 알고리즘 을 적용해야합니다.

흰색 배경과 영역의 맨하탄 (직사각형) 레이아웃 인 을 배경으로하는 문서의 경우 효율적이고 정확한 방법이 고안되었습니다. 예 에는 Baird et al.의 형상 지향 커버 알고리즘이 포함되어 있습니다. [17] 그리고 Pavlidis와 Zhou [20]에 의한 화이트 스트림 기반 세분화. 이 은 문서 이미지를 배경 구조에 따라 더 작은 영역으로 나누는 하향식 접근 방식입니다. 기본 아이디어는 이며 어떤 전경 픽셀을 포함하지 않는 최대 사각형 세트를 감지합니다.이 직사각형은 문서 이미지를 텍스트, 이미지 또는 그래픽이 포함될 수있는 영역으로 나눕니다. 영역 분류 알고리즘을 추가로 적용하기 전에 프로세싱에 적용 할 수 있습니다. 위에서 언급 한 알고리즘은 중간 결과의 표현 및 처리해야하는 많은 특별한 경우로 인해 구현이 매우 복잡합니다. Breuel [19]의 공백 커버 알고리즘 은 기하학 원리를 사용하여 같은 아이디어를 효율적으로 변형시킨 것입니다. 이 알고리즘은 특수 사례가 없기 때문에 더 간단하며이 클래스의 문서에 대해 매우 잘 수행됩니다.