[Enhancement][Core] New approaches for Page/Template Alignment

[Udayraj123]

The template alignment problem is one of the central problems which currently remains unsolved for a general OMR sheet. This issue tracks various issues that we have noticed over a period of time in various samples.

Shifts during scanning

Despite fixing page curvature, we may still face the template alignment problem. Sometimes a scanner may malfunction at minute levels, we have seen uneven stretching of the page when using a basic scanner. The boxes need to be close to the bubbles otherwise the output is not reliable for any OMR checking software.
Example:

Curvature during bulk scanning

Sometimes the scan itself seems to be curved. we can see that the instructions text is not in a straight horizontal line.
Example:

The scans need to be straightened before applying template detection.

PDF-printed vs Photocopied misalignment

We have also seen shifts upto 10 pixels between scans of pdf-printed vs photocopied sheets. Link to an explainer: Google Drive

Describe the solution you'd like
Rough notes (ref):

- **Get all control-destination points **
    - From SIFT: 
        - Filter list: Slide a 10px(windowSize) window on the image and pick the point with max score
        - Filter list: pick the points with reasonable shifts(maxDisplacement)
    - This way we can scale to any set of feature detectors like ORB or custom detectors from the ScanZones. Just need a set of control-destination pairs.

- **Align the points **
    - Approach 1: 
        - Loop over each field, find 4 nearest anchor points and
        - apply the transform on the field box using findHomography
    - Approach 2: 
        - Triangulate the whole image based on the anchor points and 
        - perform affine transform on each triangle(all pixels get transformed)

Describe alternatives you've considered
There are many other approaches that can be tried:

• cv2.findTransformECC (Enhanced Correlation Coefficient Maximization)
• Combine SIFT with ORB
• Using appropriate loss functions to use in the Visual Attention based approach
• Spatial Transformation Networks, link2
• cv2.calcOpticalFlowFarneback
• Thin Plate Spline (implemented in this ImageJ plugin)
• We can also try to apply template matching over the "margin box" of a field-label? Hard to code, can't be sure if it covers all cases. In marked bubbles case: Still score might get max in the aligned. There's also the case of current question overflowing in the next question.

Additional context
NA
Link to Discord Thread: New Approaches for Page/Template Alignment

[akashrajk54]

Hi @Udayraj123,

I’m interested in contributing to this issue and exploring solutions for improving Page/Template alignment. Based on my understanding, document scanning apps like CamScanner tackle similar alignment problems using a combination of Edge Detection, Perspective Transformation, and Image Warping techniques.

Here’s my proposed approach:

Detect Key Points & Borders: Use Canny Edge Detection + Contour Detection to find the sheet’s boundaries. Hough Line Transform can help ensure straight edges.
Correct Perspective Distortion: Apply cv2.getPerspectiveTransform to warp the scanned sheet to match the template. If curvature is present, Thin Plate Spline Warping could help.
Align the Template: Use Feature Matching (SIFT/ORB) to find control points, then apply Affine Transformation or Homography to adjust shifts.
Alternative Approaches: Testing cv2.findTransformECC or Optical Flow-based corrections for robustness.
Would love to get your feedback on this approach! Let me know if there’s a preferred direction or any specific constraints I should consider.

Looking forward to contributing! 🚀

[Udayraj123]

Hi @akashrajk54, glad to see someone showing an interest in having a go at this challenging problem.

You can start with applying Feature matching to get a basic alignment solution, for interpolating data you can explore different popular methods.

I have been following and attempting some document de-warping techniques to solve this, especially methods that make use of the layout of the page elements which is fixed per OMR Template. I have some starter code in the dev branch for this.
You can join the Discord server and discuss more with me over there.

[akashrajk54]

Hi @Udayraj123, thanks for the response! I’ll start by implementing Feature Matching for basic alignment and explore different interpolation methods. I’ll also check the dev branch to understand the existing approach.

Could you please share the Discord server link so I can join the discussion there?

[Udayraj123]

@akashrajk54 do join here: https://discord.com/channels/590134763784896514/1223641111722197042/1223641117459873832, I've updated the link in issue description as well. Feel free to ask questions especially about the template alignment code