पेज विकृति सुधार तकनीक

 (mzucker.github.io)
2 पॉइंट द्वारा GN⁺ 2024-05-14 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • मुड़े हुए दस्तावेज़ की फोटो को सपाट इमेज में बदलने के लिए 3D pose और curvature को मॉडल किया जाता है, और text reference points को align करने वाली optimization problem के रूप में हल किया जाता है
  • Leptonica और CTM की तरह text को लाइन-स्तर पर विभाजित करने के बाद, ऐसी coordinate transform खोजी जाती है जिससे लाइनें parallel और लगभग horizontal दिखें
  • मॉडल में rotation vector r, translation vector t, curvature slopes α, β, और text span के x, y offsets शामिल होते हैं, और reprojection error को न्यूनतम किया जाता है
  • पाइपलाइन page boundary cropping, text contour detection, span assembly, reference point sampling, initial value generation, Powell optimization, और cv2.remap remapping तक जाती है
  • उदाहरण रन में parameters 104~600 थे, कुल execution time 5.3~24.8 सेकंड रहा, और अधिकतर समय optimization में गया; इसलिए solver या compiled language से speed improvement की गुंजाइश है

मुड़े हुए पेज को optimization problem के रूप में हल करना

  • हस्तलिखित फोटो को PDF में बदलने वाली पुरानी script सिर्फ adaptiveThreshold और कई इमेज को PDF में बाँधने तक सीमित थी, लेकिन archival document photos में page curl के कारण text काफ़ी मुड़ जाता है
  • लक्ष्य यह है कि मुड़े हुए पेज की फोटो को अपने-आप सपाट document image में बदलने वाला प्रोग्राम बनाया जाए
  • कोड GitHub पर page_dewarp में उपलब्ध है

Leptonica और CTM से लिया गया मूल प्रवाह

  • document image dewarping पहले से जाना-पहचाना समस्या क्षेत्र है, और Dan Bloomberg की open source image processing library Leptonica में भी इसका implementation मौजूद है
  • संदर्भ सामग्री में dewarping contest results का सारांश और विजेता पद्धति Coordinate Transform Model यानी CTM से संबंधित पेपर शामिल हैं
  • Leptonica और CTM दोनों समस्या को सामान्य रूप से दो चरणों में बाँटते हैं
    • text को लाइन-स्तर पर अलग किया जाता है
    • ऐसी distortion या coordinate transform खोजी जाती है जिससे लाइनें parallel और horizontal हो जाएँ
  • यह implementation पेज के आकार को कई parameters से व्यक्त करता है
    • r, t: पेज की 3D दिशा और स्थिति बताने वाले rotation vector और translation vector
    • α, β: पेज सतह की curvature तय करने वाले दो slopes
    • y₁ ... yₙ: पेज पर मौजूद n horizontal spans के vertical offsets
    • xᵢ: हर span के भीतर कई reference points के horizontal offsets

3D curved surface और reprojection error

  • पेज का 3D आकार local y axis दिशा में एक curve को sweep करके बने surface के रूप में व्यक्त किया जाता है
  • पेज का horizontal coordinate x, surface के z दिशा displacement में map होता है, और horizontal cross-section को cubic spline से मॉडल किया जाता है
    • spline के दोनों endpoints को 0 पर fix किया जाता है
    • सिर्फ endpoint slopes α, β से spline का आकार तय होता है
  • जब pose और curvature parameters तय हो जाते हैं, तब पेज के हर (x, y) coordinate को image plane के किसी विशेष स्थान पर project किया जाता है
  • मूल फोटो में horizontal text span के keypoints खोजे जाते हैं, और initial estimate से शुरू करके keypoints की reprojection error को न्यूनतम करने वाले parameters निकाले जाते हैं
  • optimization से पहले curvature न होने की मान्यता में reprojected points एक सीधी रेखा पर होते हैं, लेकिन optimization के बाद model projection points वास्तविक detected keypoints से लगभग मेल खा जाते हैं

image processing pipeline

  • page boundary cropping

    • पूरी इमेज का उपयोग नहीं किया जाता; किनारों के अनावश्यक हिस्सों से बचने के लिए fixed margin के साथ बीच का क्षेत्र ही crop किया जाता है
    • कोई intelligent page boundary detection इस्तेमाल नहीं किया जाता

  • text contour detection

    • शुरुआत में adaptive threshold लागू किया जाता है
    • horizontal box के साथ morphological dilation) करके क्षैतिज रूप से सटे mask pixels को जोड़ा जाता है
    • vertical box के साथ erosion) करके एक-pixel ऊँचाई वाले noise को हटाया जाता है
    • connected component analysis के बाद बहुत ऊँचे या बहुत मोटे blobs को फ़िल्टर किया जाता है
    • बचे हुए text contours को PCA से best-fit line segment के रूप में approximate किया जाता है

  • horizontal line detection का पूरक

    • कुछ inputs में vertical text वाले table रूप अधिक थे, इसलिए यदि पर्याप्त horizontal text detect नहीं होता, तो horizontal lines या rules का detection भी आज़माया जाता है

text span बनाना और reference point sampling

  • detected contours को एक ही horizontal span में बाँधने के लिए सभी contour pairs के लिए candidate edges बनाए जाते हैं और उनका cost निकाला जाता है
  • यदि दो contours लंबाई दिशा में बहुत अधिक overlap करते हों, बहुत दूर हों, या उनके angles में बहुत अंतर हो, तो cost को अनंत रखा जाता है
  • वैध edges का cost दूरी और angle change के linear combination से निकाला जाता है
  • edges को cost के अनुसार sort करने के बाद, तभी connect किया जाता है जब दोनों तरफ़ के contours अभी तक जुड़े न हों; इसके लिए greedy quadratic-time तरीका अपनाया जाता है
    • क्योंकि execution time का अधिकांश हिस्सा optimization में जाता है, इसलिए इस चरण की quadratic time complexity बड़ी समस्या नहीं थी
  • span बनने के बाद, बहुत छोटे spans हटा दिए जाते हैं जो मॉडल तय करने में उपयोगी नहीं होते
  • parameter model को discrete reference points चाहिए, इसलिए text contour पर लगभग हर 20 pixels पर एक keypoint चुना जाता है

initial values बनाना और Powell optimization

  • सभी spans की औसत दिशा PCA से estimate की जाती है
  • PCA परिणाम के principal components का उपयोग करके शुरुआती x, y coordinates और सपाट, बिना curvature वाले पेज की pose को analytically set किया जाता है
  • reprojection में cubic spline को sample करके object points का z offset निकाला जाता है, और फिर OpenCV functions से उन्हें image plane पर project किया जाता है
    • cv2.solvePnP
    • cv2.projectPoints
  • reprojection error को न्यूनतम करने के लिए scipy.optimize.minimize और 'Powell' solver का उपयोग किया जाता है
    • इसे black-box, derivative-free optimization tool की तरह इस्तेमाल किया जाता है
    • समस्या स्वयं non-linear least squares की श्रेणी में आती है
    • अन्य solvers या विशेष non-linear least squares solvers के साथ अधिक प्रयोग नहीं किया गया
  • प्रोग्राम के execution time का लगभग 100% इसी optimization चरण में खर्च होता है

remapping और output image generation

  • optimization समाप्त होने के बाद r, t, α, β को अलग करके coordinate transform बनाई जाती है
  • वास्तविक dewarp, 3D page points की dense mesh को cv2.projectPoints से project करके और उन image coordinates को cv2.remap में देकर किया जाता है
  • अंतिम परिणाम cv2.adaptiveThreshold और Pillow का उपयोग करके bi-level PNG के रूप में सेव किया जाता है

उदाहरण परिणाम और execution time

  • GitHub repository में कई example images शामिल हैं
  • एकल 2012 MacBook Pro पर रन किए गए आँकड़े इस प्रकार हैं
इनपुट Spans Keypoints Parameters Optimization time Total time
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 parameters हैं, और सबसे बड़े मॉडल में 600, इसलिए यह कोई छोटा optimization problem नहीं है
  • optimization speed को अन्य तरीकों या compiled language के उपयोग से बेहतर किया जा सकता है

बची हुई सीमाएँ

  • पूरा दृष्टिकोण थोड़ा background knowledge पढ़कर पूरी समस्या को optimization process के output के रूप में formulate करने पर आधारित है
  • यह तरीका deformable part models और active appearance models की याद दिलाता है, लेकिन उतना परिष्कृत नहीं है
  • Leptonica और CTM सिर्फ vertical distortion ही नहीं, बल्कि horizontal distortion को भी मॉडल और correct करने की कोशिश करते हैं
  • यह implementation horizontal distortion correction तक नहीं जाता
    • क्योंकि cubic spline arc-length parameterization नहीं है, spline slope अधिक होने वाले क्षेत्रों में text थोड़ा compressed दिखता है
    • प्रोजेक्ट मुख्यतः proof-of-concept था, इसलिए इस समस्या पर आगे काम नहीं किया गया
  • अंतिम कोड GitHub repository में उपलब्ध है, लेकिन विस्तृत comments अभी भी पर्याप्त नहीं हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-05-14
Hacker News की राय

  • लेखक ने जैसा किया है, आउटपुट पर कड़ा thresholding लागू करते समय सावधान रहना चाहिए
    सामान्य text pages तो काफ़ी अच्छी तरह पकड़ में आ जाते हैं, लेकिन Google Books के कई pages में मैंने illustrations या छोटे footnotes को पढ़ने लायक न रहने तक बिगड़ते देखा है
    अगर Google Books scan ही इकलौता source हो, तो आप पूरी तरह अटक जाते हैं

    • क्या thresholding का इस्तेमाल dewarping parameters चुनने के लिए reference points खोजने के मकसद से नहीं है?
      एक बार reference points मिल जाएँ, तो वे parameters original image पर लागू किए जा सकते हैं

  • 2024 में भी document scanner apps में यह feature default रूप से built-in क्यों नहीं है, यह झुंझलाने वाला है

    • मैं स्कूल में GeniusScan इस्तेमाल करता हूँ और उसमें यह feature है: https://blog.thegrizzlylabs.com/2024/03/genius-scan-7.16.htm...
    • बहुत अच्छा है
      optimize करने के लिए low-dimensional page deformation model रखना इस approach के अच्छी तरह काम करने की मुख्य वजह लगता है
      यह YC scale के लिए बिल्कुल सही problem है। market launch तक कुछ हफ्ते, और launch cost शायद कुछ लाख dollars के आसपास होगी
      Apple के phone app में बहुत ज़्यादा manual adjustment चाहिए, और Microsoft के Office Lens / Microsoft Lens के बारे में “edges आखिरकार पागल हो जाते हैं और भयानक दिखते हैं” जैसी reviews हैं
      इसलिए बस ठीक से काम करने वाले product का market है, और आम acquisition candidates को बेचकर exit भी संभव लगता है
    • लगता है Google Drive पहले यह ठीक से करता था, लेकिन पिछले कुछ वर्षों में यह काफ़ी खराब हो गया है
    • product management ने शायद माना होगा कि technical risk लेने लायक नहीं है
      उन्हें यह बहुत complex और mathematical लगा होगा, और इसके बजाय उन्होंने सोचा होगा कि users की social media activity खंगालकर notification timing को और fine-tune करने वाला model बनाना user metrics को बेहतर करेगा
      churn कम करने की कोशिश में decision-makers ने सख्ती से data-driven तरीके से फैसला लिया होगा
    • vflat इस काम के लिए अच्छा है

  • John Warnock ने Adobe CEO पद छोड़ने के बाद दुर्लभ ऐतिहासिक किताबों को preserve करने वाली company Octavo में और गहराई से काम किया
    उनके सामने आई चुनौतियों में से एक ऐसी scanned pages की curling को सीधा करना था जिन्हें दबाकर पूरी तरह फैलाया नहीं जा सकता था
    https://en.m.wikipedia.org/wiki/Rare_Book_Room

  • लेख शानदार था
    technical project और उससे जुड़े decisions को प्रभावी ढंग से document कैसे किया जा सकता है, इसके उदाहरण के तौर पर company में भी reference लिया जा सकता है

  • university में colour-coded notes scan करने वाला app बनाने की कोशिश करते समय मुझे एक अलग problem मिली थी
    page पर ऊपर से नीचे जाते हुए colour shift हो जाता था, जिससे blue pen और green pen को भरोसेमंद तरीके से अलग करना मुश्किल था
    कभी फिर से इसे देखना चाहिए

    • अगर मान लें कि white background भी उसी तरह shift हो रहा है, तो image को copy करके बहुत ज़्यादा blur करना और फिर original image को उस blurred version से divide करना एक अच्छा trick है
      इससे low-frequency colour/brightness variation प्रभावी रूप से हट जाता है
      कागज़ की photo लेने पर shadows हटाने के लिए इसका अक्सर इस्तेमाल होता है, और लगता है colour gradients पर भी यह वैसा ही काम करेगा

  • काफ़ी ठीक लगता है
    हालांकि deformation model थोड़ा ज़्यादा global लगता है
    कागज़ की कुछ ज़्यादा complex distortions model में capture नहीं होतीं, और final result में भी residual distortion के रूप में दिखती हैं

  • install के दौरान error आया:
    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 issue खोल दिया है

  • बहुत शानदार
    mobile पर इस्तेमाल करने लायक कोई अच्छा document scanning app हो तो अच्छा होगा—जिसमें dewarping, thresholding और PDF generation सब ठीक से हो
    अभी मैं Adobe Scan में फँसा हूँ, जिसके results तुलनात्मक रूप से सबसे अच्छे हैं, लेकिन उसका dewarping फिर भी काफ़ी खराब है

    • मैंने सुना है Microsoft Lens अच्छा है, लेकिन मेरे phone पर खोलते ही बस freeze हो जाता है

  • पढ़ना वाकई दिलचस्प था
    लगता है 2016 में छूटा हुआ लेख है, लेकिन “यह problem थी, एक smart technique लगाई और अच्छी तरह काम करने वाला solution मिला” वाला पूरा flow साफ दिखता है, यह अच्छा लगा
    व्यक्तिगत रूप से शायद मुझे इसकी कभी ज़रूरत न पड़े, लेकिन यह problem को अच्छे तरीके से handle करने और output तथा expectations की अनुमति वाली सीमा में समझदारी से compromise करने का बढ़िया उदाहरण है
    लेख भी अच्छी तरह लिखा गया है और explanation भी अच्छा है

  • अगर किताब को visually दिखाने की ज़रूरत नहीं है और सिर्फ OCR करना है, तो शायद यह step skip किया जा सकता है
    Google ने यह problem 10 साल से भी पहले solve कर ली थी: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
    अगर manuscript सचमुच valuable है, तो X-ray tomography से non-contact dewarping भी संभव है: https://scrollprize.org/tutorial1

    • तो फिर कोई usable software ढूँढकर recommend कर देना चाहिए
      Google वाली चीज़ में hardware इस्तेमाल हुआ था, और X-ray tomography वाली बात काफ़ी ChatGPT जैसी लगती है
      फिर भी इस लेख का तरीका 2016 के हिसाब से अच्छा और simple है