페이지 왜곡 보정 기술

 (mzucker.github.io)
2P by GN⁺ | ★ favorite | 댓글 1개
  • 구부러진 문서 사진을 평평한 이미지로 바꾸기 위해 3D 자세와 곡률을 모델링하고, 텍스트 기준점을 맞추는 최적화 문제로 풀어냄
  • Leptonica와 CTM처럼 텍스트를 줄 단위로 나눈 뒤, 줄들이 평행하고 수평에 가깝게 보이도록 좌표 변환을 찾는 흐름을 따름
  • 모델은 회전 벡터 r, 이동 벡터 t, 곡률 기울기 α, β, 텍스트 span의 x, y 오프셋을 포함하며 재투영 오차를 최소화함
  • 파이프라인은 페이지 경계 자르기, 텍스트 윤곽 검출, span 조립, 기준점 샘플링, 초기값 생성, Powell 최적화, cv2.remap 재매핑으로 이어짐
  • 예제 실행에서 파라미터는 104~600개, 총 실행 시간은 5.3~24.8초였고 대부분이 최적화에 쓰여 solver나 컴파일 언어로 속도 개선 여지가 남음

구부러진 페이지를 최적화 문제로 풀기

  • 손글씨 사진을 PDF로 만드는 기존 스크립트는 adaptiveThreshold와 여러 이미지를 PDF로 묶는 수준이었지만, 보관 문서 사진에서는 페이지 말림 때문에 텍스트가 크게 휘어짐
  • 목표는 구부러진 페이지 사진을 자동으로 평평한 문서 이미지로 변환하는 프로그램을 만드는 것임
  • 코드는 GitHub의 page_dewarp에 공개되어 있음

Leptonica와 CTM에서 가져온 기본 흐름

  • 문서 이미지 왜곡 보정은 이미 알려진 문제이며, Dan Bloomberg의 오픈소스 이미지 처리 라이브러리 Leptonica에도 구현되어 있음
  • 참고 자료에는 dewarping contest 결과 요약과 우승 방식인 Coordinate Transform Model, 즉 CTM 관련 논문이 포함됨
  • Leptonica와 CTM은 문제를 공통적으로 두 단계로 나눔
    • 텍스트를 줄 단위로 분리함
    • 줄들이 평행하고 수평이 되도록 왜곡 또는 좌표 변환을 찾음
  • 이 구현은 페이지 외형을 여러 파라미터로 표현함
    • r, t: 페이지의 3D 방향과 위치를 나타내는 회전 벡터와 이동 벡터
    • α, β: 페이지 표면 곡률을 정하는 두 기울기
    • y₁ ... yₙ: 페이지 위 n개 수평 span의 세로 오프셋
    • xᵢ: 각 span 안의 여러 기준점에 대한 가로 오프셋

3D 곡면과 재투영 오차

  • 페이지의 3D 형태는 로컬 y축 방향으로 곡선을 쓸어 만든 표면으로 표현함
  • 페이지의 가로 좌표 x는 표면의 z 방향 변위로 매핑되며, 수평 단면은 3차 스플라인으로 모델링함
    • 스플라인 양 끝점은 0으로 고정됨
    • 끝점 기울기 α, β만으로 스플라인 형태가 정해짐
  • 자세와 곡률 파라미터가 정해지면, 페이지의 각 (x, y) 좌표가 이미지 평면의 특정 위치로 투영됨
  • 원본 사진에서 수평 텍스트 span의 keypoint를 찾고, 초기 추정값에서 시작해 keypoint의 재투영 오차를 최소화하는 파라미터를 찾음
  • 최적화 전에는 곡률이 없다고 가정해 재투영점이 일직선에 놓이지만, 최적화 후에는 모델 투영점이 실제 검출 keypoint에 거의 겹침

이미지 처리 파이프라인

  • 페이지 경계 자르기

    • 이미지 전체를 쓰지 않고, 가장자리의 불필요한 영역을 피하기 위해 고정 margin으로 가운데 영역만 잘라냄
    • 지능적인 페이지 경계 검출은 사용하지 않음

  • 텍스트 윤곽 검출

    • 초기 adaptive threshold를 적용함
    • 수평 박스로 morphological dilation)을 수행해 가로로 인접한 마스크 픽셀을 연결함
    • 수직 박스로 erosion)을 수행해 한 픽셀 높이의 잡음을 제거함
    • connected component analysis 뒤, 너무 높거나 두꺼운 blob을 걸러냄
    • 남은 텍스트 윤곽은 PCA로 가장 잘 맞는 선분으로 근사함

  • 수평선 검출 보완

    • 일부 입력은 세로 텍스트가 많은 표 형태였기 때문에, 수평 텍스트가 충분히 검출되지 않으면 수평선이나 rule 검출도 시도함

텍스트 span 구성과 기준점 샘플링

  • 검출된 윤곽들을 같은 수평 span에 묶기 위해 모든 윤곽 쌍에 대해 후보 edge를 만들고 비용을 계산함
  • 두 윤곽이 길이 방향으로 크게 겹치거나 너무 멀거나 각도가 많이 벌어지면 비용을 무한대로 둠
  • 유효한 edge의 비용은 거리와 각도 변화의 선형 조합으로 계산됨
  • edge를 비용순으로 정렬한 뒤, 양쪽 윤곽이 아직 연결되지 않았을 때만 연결하는 탐욕적 이차 시간 방식을 사용함
    • 실행 시간 대부분이 최적화에 쓰이므로 이 단계의 이차 시간 복잡도는 큰 문제가 아니었음
  • span이 만들어진 뒤에는 너무 작아 모델 결정에 도움이 되지 않는 span을 제거함
  • 파라미터 모델에는 이산 기준점이 필요하므로, 텍스트 윤곽 약 20픽셀마다 keypoint 하나를 선택함

초기값 생성과 Powell 최적화

  • 모든 span의 평균 방향은 PCA로 추정함
  • PCA 결과의 주성분을 이용해 초기 x, y 좌표와 평평한 무곡률 페이지의 자세를 해석적으로 설정함
  • 재투영은 3차 스플라인을 샘플링해 객체점의 z 오프셋을 얻고, OpenCV 함수로 이미지 평면에 투영함
    • cv2.solvePnP
    • cv2.projectPoints
  • 재투영 오차 최소화에는 scipy.optimize.minimize와 'Powell' solver를 사용함
    • 블랙박스 방식의 미분 없는 최적화 도구로 사용됨
    • 문제 자체는 비선형 최소제곱에 해당함
    • 다른 solver나 특화된 비선형 최소제곱 solver는 많이 실험하지 않음
  • 프로그램 실행 시간의 거의 100%가 이 최적화 단계에 쓰임

재매핑과 출력 이미지 생성

  • 최적화가 끝나면 r, t, α, β만 분리해 좌표 변환을 만듦
  • 실제 dewarp는 3D 페이지 점들의 dense mesh를 cv2.projectPoints로 투영하고, 그 이미지 좌표를 cv2.remap에 전달해 얻음
  • 최종 결과는 cv2.adaptiveThreshold와 Pillow를 사용해 bi-level PNG로 저장함

예제 결과와 실행 시간

  • GitHub 저장소에는 여러 example images가 포함되어 있음
  • 단일 2012 MacBook Pro 실행 기준 통계는 다음과 같음
입력 Spans Keypoints Parameters 최적화 시간 총 시간
boston_cooking_a.jpg 38 554 600 23.3초 24.8초
boston_cooking_b.jpg 38 475 521 18.0초 18.8초
linguistics_thesis_a.jpg 20 161 189 5.1초 6.1초
linguistics_thesis_b.jpg 7 89 104 4.2초 5.3초
  • 가장 작은 모델도 파라미터가 104개이고, 가장 큰 모델은 600개라서 작은 최적화 문제는 아님
  • 최적화 속도는 다른 방법을 시도하거나 컴파일 언어를 사용하면 개선될 수 있음

남은 한계

  • 전체 접근은 배경 지식을 조금 읽고, 문제 전체를 최적화 과정의 출력으로 공식화하는 방식임
  • 이 방식은 deformable part models와 active appearance models를 떠올리게 하지만, 둘만큼 정교하지는 않음
  • Leptonica와 CTM은 수직 왜곡뿐 아니라 수평 왜곡도 모델링하고 보정하려고 시도함
  • 이 구현은 수평 왜곡 보정까지 다루지 않음
    • 3차 스플라인이 arc-length 파라미터화가 아니기 때문에, 스플라인 기울기가 큰 영역에서는 텍스트가 약간 압축됨
    • 프로젝트가 주로 proof-of-concept였기 때문에 이 문제는 더 진행하지 않음
  • 최종 코드는 GitHub 저장소에 공개되어 있으며, 자세한 주석 보강은 아직 충분하지 않음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 저자가 한 것처럼 출력에 강한 임계값 처리를 적용하는 건 조심해야 함
    일반 텍스트 페이지는 꽤 잘 잡지만, Google Books의 여러 페이지에서 삽화나 작은 각주가 읽을 수 없을 만큼 망가지는 걸 봤음
    Google Books 스캔본이 유일한 자료라면 완전히 막히게 됨

    • 임계값 처리는 왜곡 보정 매개변수를 고르기 위한 기준점을 찾는 용도 아닌가?
      일단 기준점을 찾으면 그 매개변수를 원본 이미지에 적용할 수 있을 것 같음

  • 2024년인데 왜 문서 스캐너 앱에 이런 기능이 아직도 기본 내장되어 있지 않은지 답답함

    • 학교에서 GeniusScan을 쓰는데 이 기능이 있음: https://blog.thegrizzlylabs.com/2024/03/genius-scan-7.16.htm...
    • 아주 좋음
      최적화할 저차원 페이지 변형 모델을 둔 게 이 방식이 잘 동작하는 핵심처럼 보임
      이건 YC 규모에 딱 맞는 문제임. 시장 출시까지 몇 주, 출시 비용은 수십만 달러 정도면 될 듯함
      Apple의 휴대폰 앱은 수동 조정이 너무 많이 필요하고, Microsoft의 Office Lens / Microsoft Lens에는 “가장자리가 결국 미쳐 날뛰고 끔찍해 보인다” 같은 평가가 있음
      그러니 그냥 잘 동작하는 제품의 시장이 있고, 흔한 인수 후보들에게 매각하는 식의 엑시트도 가능해 보임
    • Google Drive가 예전에는 이걸 제대로 했던 것 같은데, 지난 몇 년 사이에 훨씬 나빠졌다고 느낌
    • 제품 관리는 기술 리스크가 감당할 가치가 없다고 봤을 것 같음
      너무 복잡하고 수학적이라 여겼고, 대신 사용자의 소셜 미디어 활동을 훑어서 알림 타이밍을 더 정교하게 잡는 모델을 만들면 사용자 지표가 더 좋아질 거라고 판단했을 듯함
      이탈률을 줄이려는 과정에서 의사결정권자들이 엄격하게 데이터 기반으로 결정한 셈임
    • vflat이 이 용도로 좋음

  • John Warnock이 Adobe CEO에서 물러난 뒤, 희귀 역사서를 보존하는 회사 Octavo에 더 깊이 관여했음
    그들이 마주한 과제 중 하나가 눌러 펼칠 수 없는 스캔 페이지의 말림을 펴는 일이었음
    https://en.m.wikipedia.org/wiki/Rare_Book_Room

  • 글이 훌륭했음
    기술 프로젝트와 그 의사결정을 어떻게 효과적으로 문서화할 수 있는지 보여주는 예시로 회사에서 참고할 수도 있겠음

  • 대학 때 색으로 구분한 노트를 스캔하는 앱을 만들려다 다른 문제를 만났음
    페이지 위에서 아래로 갈수록 색이 틀어져서 파란 펜과 초록 펜을 안정적으로 구분하기 어려웠음
    언젠가 다시 들여다봐야겠음

    • 흰 배경도 같은 방식으로 틀어진다고 가정하면, 이미지를 복사해 아주 크게 흐림 처리한 뒤 원본 이미지를 그 흐린 버전으로 나누는 게 좋은 요령임
      이렇게 하면 저주파 색상/밝기 변화가 사실상 제거됨
      종이를 사진으로 찍었을 때 그림자를 없애는 데 자주 쓰는데, 색상 그라데이션에도 똑같이 통할 것 같음

  • 충분히 괜찮아 보임
    다만 변형 모델이 조금 지나치게 전역적인 것 같음
    종이의 더 복잡한 왜곡 일부가 모델에 잡히지 않고, 최종 결과에서도 잔여 왜곡으로 보임

  • 설치 중 오류가 남:
    ERROR: Could not find a version that satisfies the requirement cv2>=3.0 (from versions: none)
    ERROR: No matching distribution found for cv2>=3.0
    GitHub 이슈를 올렸음

  • 아주 멋짐
    모바일에서 쓸 수 있는 괜찮은 문서 스캔 앱이 있으면 좋겠음. 왜곡 보정, 임계값 처리, PDF 생성까지 잘 되는 앱 말임
    지금은 결과가 그나마 제일 나은 Adobe Scan에 묶여 있는데, 그래도 왜곡 보정은 꽤 별로임

    • Microsoft Lens가 좋다는 얘기는 들었지만, 내 휴대폰에서 열어보면 그냥 멈춰버림

  • 읽기 정말 흥미로웠음
    2016년에 놓친 글 같은데, “이 문제가 있었고, 똑똑한 기법을 적용해 잘 동작하는 해법을 얻었다”는 전체 흐름이 잘 드러나서 좋음
    개인적으로 이런 게 필요할 일은 없을 것 같지만, 좋은 방법으로 문제를 다루고 출력 결과와 기대치가 허용하는 범위에서 적당히 타협하는 훌륭한 예시임
    글도 잘 쓰였고 설명도 좋음

  • 책을 시각적으로 보여줄 필요가 없고 OCR만 하면 된다면 이 단계를 건너뛸 수 있을 것 같음
    Google은 10년도 더 전에 이 문제를 해결했음: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
    원고가 정말 가치 있다면 X선 단층촬영으로 비접촉 왜곡 보정도 가능함: https://scrollprize.org/tutorial1

    • 그렇다면 쓸 만한 소프트웨어를 찾아서 추천해보면 됨
      Google 쪽은 하드웨어를 썼고, X선 단층촬영 얘기는 ChatGPT 느낌이 강함
      그래도 이 글의 방식은 2016년 기준으로 보기 좋고 단순함
답변달기