Close Menu
    Trending
    • Creating AI that matters | MIT News
    • Scaling Recommender Transformers to a Billion Parameters
    • Hidden Gems in NumPy: 7 Functions Every Data Scientist Should Know
    • Is RAG Dead? The Rise of Context Engineering and Semantic Layers for Agentic AI
    • ChatGPT Gets More Personal. Is Society Ready for It?
    • Why the Future Is Human + Machine
    • Why AI Is Widening the Gap Between Top Talent and Everyone Else
    • Implementing the Fourier Transform Numerically in Python: A Step-by-Step Guide
    ProfitlyAI
    • Home
    • Latest News
    • AI Technology
    • Latest AI Innovations
    • AI Tools & Technologies
    • Artificial Intelligence
    ProfitlyAI
    Home » Classical Computer Vision and Perspective Transformation for Sudoku Extraction
    Artificial Intelligence

    Classical Computer Vision and Perspective Transformation for Sudoku Extraction

    ProfitlyAIBy ProfitlyAIOctober 5, 2025No Comments12 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Share
    Facebook Twitter LinkedIn Pinterest Email


    of AI hype, it appears like everyone seems to be utilizing Imaginative and prescient-Language Fashions and enormous Imaginative and prescient Transformers for each downside in Laptop Imaginative and prescient. Many individuals see these instruments as one-size-fits-all options and instantly use the newest, shiniest mannequin as a substitute of understanding the underlying sign they need to extract. However oftentimes there’s magnificence to simplicity. It’s some of the necessary classes I’ve realized as an engineer: don’t overcomplicate options to easy issues.

    Animation of processing pipeline
    Processing pipeline steps animated

    Let me present you a sensible software of some easy classical Laptop Imaginative and prescient strategies to detect rectangular objects on flat surfaces and apply a perspective transformation to rework the skewed rectangle. Comparable strategies are extensively used, for instance, in doc scanning and extraction functions.

    Alongside the best way you’ll study some attention-grabbing ideas from commonplace classical Laptop Imaginative and prescient strategies to methods to order polygon factors and why that is associated to a combinatoric project downside.

    Overview
    • Detection
      • Grayscale
      • Edge Detection
      • Dilation
      • Contour Detection
    • Perspective Transformation
      • Variant A: Easy kind primarily based on sum/diff
      • Variant B: Task Optimization Downside
      • Variant C: Cyclic sorting with anchor
      • Making use of the Perspective Transformation
    • Conclusion

    Detection

    To detect Sudoku grids I thought of many alternative approaches starting from easy thresholding, hough line transformations or some type of edge detection to coaching a deep studying mannequin for segmentation or keypoint detection.

    Let’s outline some assumptions to scope the issue:

    1. The Sudoku grid is clearly and absolutely seen within the body with a transparent quadrilateral border, with sturdy distinction from the background.
    2. The floor on which the Sudoku grid is printed must be flat, however may be captured from an angle and seem skewed or rotated.
    Examples for different image qualities
    Examples for various picture qualities

    I’ll present you a easy pipeline with some filtering steps to detect the bounds of our Sudoku grid. On a excessive degree, the processing pipeline seems to be as follows:

    Diagram of processing pipeline steps
    Visualization of processing pipeline steps
    Visualization of processing pipeline steps

    Grayscale

    On this first step we merely convert the enter picture from its three shade channels to a single channel grayscale picture, as we don’t want any shade data to course of these pictures.

    def find_sudoku_grid(
        picture: np.ndarray,
    ) -> np.ndarray | None:
        """
        Finds the most important square-like contour in a picture, possible the Sudoku grid.
    
        Returns:
            The contour of the discovered grid as a numpy array, or None if not discovered.
        """
    
        grey = cv2.cvtColor(picture, cv2.COLOR_BGR2GRAY)

    Edge Detection

    After changing the picture to grayscale we will use the Canny edge detection algorithm to extract edges. There are two thresholds to decide on for this algorithm that decide if pixels are accepted as edges:

    Canny edge thresholds explained
    Thresholds of Canny edge detection

    In our case of detecting Sudoku grids, we assume very sturdy edges on the border strains of our grid. We are able to select a excessive higher threshold to reject noise from showing in our masks, and a decrease threshold not too low to reject small noisy edges linked to the principle border from displaying up in our masks.

    A blur filter is usually used earlier than passing pictures to Canny to scale back noise, however on this case the sides are very sturdy however slim, therefore the blur is omitted.

    def find_sudoku_grid(
        picture: np.ndarray,
        canny_threshold_1: int = 100,
        canny_threshold_2: int = 255,
    ) -> np.ndarray | None:
        """
        Finds the most important square-like contour in a picture, possible the Sudoku grid.
    
        Args:
            picture: The enter picture.
            canny_threshold_1: Decrease threshold for the Canny edge detector.
            canny_threshold_2: Higher threshold for the Canny edge detector.
    
        Returns:
            The contour of the discovered grid as a numpy array, or None if not discovered.
        """
    
        ...
    
        canny = cv2.Canny(grey, threshold1=canny_threshold_1, threshold2=canny_threshold_2)
    Masks picture after Canny edge

    Dilation

    On this subsequent step, we post-process the sting detection masks with a dilation kernel to shut small gaps within the masks.

    def find_sudoku_grid(
        picture: np.ndarray,
        canny_threshold_1: int = 100,
        canny_threshold_2: int = 255,
        morph_kernel_size: int = 3,
    ) -> np.ndarray | None:
        """
        Finds the most important square-like contour in a picture, possible the Sudoku grid.
    
        Args:
            picture: The enter picture.
            canny_threshold_1: First threshold for the Canny edge detector.
            canny_threshold_2: Second threshold for the Canny edge detector.
            morph_kernel_size: Dimension of the morphological operation kernel.
    
        Returns:
            The contour of the discovered grid as a numpy array, or None if not discovered.
        """
    
        ...
    
        kernel = cv2.getStructuringElement(
            form=cv2.MORPH_RECT, ksize=(morph_kernel_size, morph_kernel_size)
        )
        masks = cv2.morphologyEx(canny, op=cv2.MORPH_DILATE, kernel=kernel, iterations=1)
    Masks picture after Dilation

    Contour Detection

    Now that the binary masks is prepared, we will run a contour detection algorithm to search out coherent blobs and filter right down to a single contour with 4 factors.

    contours, _ = cv2.findContours(
        masks, mode=cv2.RETR_EXTERNAL, technique=cv2.CHAIN_APPROX_SIMPLE
    )
    Detected contours on masks picture

    This preliminary contour detection will return a listing of contours that include each single pixel that’s a part of the contour. We are able to use the Douglas–Peucker algorithm to iteratively cut back the variety of factors within the contour and approximate the contour with a easy polygon. We are able to select a minimal distance between factors for the algorithm.

    If we assume that even for among the most skewed rectangle, the shortest facet is a minimum of 10% of the circumference of the form, we will filter the contours right down to polygons with precisely 4 factors.

    contour_candidates: checklist[np.ndarray] = []
    for cnt in contours:
        # Approximate the contour to a polygon
        epsilon = 0.1 * cv2.arcLength(curve=cnt, closed=True)
        approx = cv2.approxPolyDP(curve=cnt, epsilon=epsilon, closed=True)
    
        # Maintain solely polygons with 4 vertices
        if len(approx) == 4:
            contour_candidates.append(approx)

    Lastly we take the most important detected contour, presumably the ultimate Sudoku grid. We kind the contours by space in reverse order after which take the primary factor, equivalent to the most important contour space.

    best_contour = sorted(contour_candidates, key=cv2.contourArea, reverse=True)[0]
    Filtered contour highlighted on authentic picture

    Perspective Transformation

    Lastly we have to remodel the detected grid again to its sq.. To realize this, we will use a perspective transformation. The transformation matrix may be calculated by specifying the place the 4 factors of our Sudoku grid contour must be positioned in the long run: the 4 corners of the picture.

    rect_dst = np.array(
        [[0, 0], [width - 1, 0], [width - 1, height - 1], [0, height - 1]],
    )

    To match the contour factors to the corners, they must be ordered first, to allow them to be assigned appropriately. Let’s outline the next order for our nook factors:

    Variant A: Easy kind primarily based on sum/diff

    To kind the extracted corners and assign them to those goal factors, a easy algorithm might take a look at the sum and variations of the x and y coordinates for every nook.

    p_sum = p_x + p_y
    p_diff = p_x - p_y

    Primarily based on these values, it’s now potential to distinguish the corners:

    • The highest left nook has each a small x and y worth, it has the smallest sum argmin(p_sum)
    • Backside proper nook has the most important sum argmax(p_sum)
    • High proper nook has the most important diff argmax(p_diff)
    • Backside left nook has the smallest distinction argmin(p_diff)

    Within the following animation, I attempted to visualise this project of the 4 corners of a rotating sq.. The coloured strains characterize the respective picture nook assigned to every sq. nook.

    Animation of a rotating square, each corner with a different color and lines indicating the assignment to image corners
    Animation of a rotating sq., every nook with a distinct shade and contours indicating the project to picture corners
    def order_points(pts: np.ndarray) -> np.ndarray:
        """
        Orders the 4 nook factors of a contour in a constant
        top-left, top-right, bottom-right, bottom-left sequence.
    
        Args:
            pts: A numpy array of form (4, 2) representing the 4 corners.
    
        Returns:
            A numpy array of form (4, 2) with the factors ordered.
        """
        # Reshape from (4, 1, 2) to (4, 2) if wanted
        pts = pts.reshape(4, 2)
        rect = np.zeros((4, 2), dtype=np.float32)
    
        # The highest-left level could have the smallest sum, whereas
        # the bottom-right level could have the most important sum
        s = pts.sum(axis=1)
        rect[0] = pts[np.argmin(s)]
        rect[2] = pts[np.argmax(s)]
    
        # The highest-right level could have the smallest distinction,
        # whereas the bottom-left could have the most important distinction
        diff = np.diff(pts, axis=1)
        rect[1] = pts[np.argmin(diff)]
        rect[3] = pts[np.argmax(diff)]
    
        return rect

    This works nicely until the rectangle is closely skewed, like the next one. On this case, you’ll be able to clearly see that this technique is flawed, as there the identical rectangle nook is assigned a number of picture corners.

    Same assignment procedure fails with a skewed rotating quadrilateral shape
    Similar project process fails with a skewed rotating quadrilateral form

    Variant B: Task Optimization Downside

    One other method can be to reduce the distances between every level and its assigned nook. This may be applied utilizing a pairwise_distances calculation between every level and the corners and the linear_sum_assignment perform from scipy, which solves the project downside whereas minimizing a price perform.

    def order_points_simplified(pts: np.ndarray) -> np.ndarray:
        """
        Orders a set of factors to finest match a goal set of nook factors.
    
        Args:
            pts: A numpy array of form (N, 2) representing the factors to order.
    
        Returns:
            A numpy array of form (N, 2) with the factors ordered.
        """
        # Reshape from (N, 1, 2) to (N, 2) if wanted
        pts = pts.reshape(-1, 2)
    
        # Calculate the space between every level and every goal nook
        D = pairwise_distances(pts, pts_corner)
    
        # Discover the optimum one-to-one project
        # row_ind[i] needs to be matched with col_ind[i]
        row_ind, col_ind = linear_sum_assignment(D)
    
        # Create an empty array to carry the sorted factors
        ordered_pts = np.zeros_like(pts)
    
        # Place every level within the appropriate slot primarily based on the nook it was matched to.
        # For instance, the purpose matched to target_corners[0] goes into ordered_pts[0].
        ordered_pts[col_ind] = pts[row_ind]
    
        return ordered_pts
    Animated rotating skewed quadrilaterl with corners assigned correctly to image corners
    Animated rotating skewed quadrilateral with corners assigned appropriately to picture corners

    Regardless that this resolution works, it isn’t ideally suited, because it depends on the picture distance between the form factors and the corners and it’s computationally dearer as a result of a distance matrix needs to be constructed. In fact right here within the case of 4 factors assigned that is negligible, however this resolution wouldn’t be nicely suited to a polygon with many factors!

    Variant C: Cyclic sorting with anchor

    This third variant is a really light-weight and environment friendly strategy to kind and assign the factors of the form to the picture corners. The thought is to calculate an angle for every level of the form primarily based on the centroid place.

    Sketch of angles assigned to each corner
    Sketch of angles assigned to every nook

    For the reason that angles are cyclic, we have to select an anchor to ensure absolutely the order of the factors. We merely choose the purpose with the bottom sum of x and y.

    def order_points(self, pts: np.ndarray) -> np.ndarray:
        """
        Orders factors by angle across the centroid, then rotates to begin from top-left.
    
        Args:
            pts: A numpy array of form (4, 2).
    
        Returns:
            A numpy array of form (4, 2) with factors ordered."""
        pts = pts.reshape(4, 2)
        middle = pts.imply(axis=0)
        angles = np.arctan2(pts[:, 1] - middle[1], pts[:, 0] - middle[0])
        pts_cyclic = pts[np.argsort(angles)]
        sum_of_coords = pts_cyclic.sum(axis=1)
        top_left_idx = np.argmin(sum_of_coords)
        return np.roll(pts_cyclic, -top_left_idx, axis=0)
    Animated rotating skewed quadrilaterl with corners assigned correctly with angle assignment method
    Animated rotating skewed quadrilaterl with corners assigned appropriately with angle project technique

    We are able to now use this perform to kind our contour factors:

    rect_src = order_points(grid_contour)

    Making use of the Perspective Transformation

    Now that we all know which factors must go the place, we will lastly transfer on to essentially the most attention-grabbing half: creating and truly making use of the angle transformation to the picture.

    Animation of applying perspective transformation
    Animation of making use of perspective transformation

    Since we have already got our checklist of factors for the detected quadrilateral sorted in rect_src, and we’ve got our goal nook factors in rect_dst, we will use the OpenCV technique for calculating the transformation matrix:

    warp_mat = cv2.getPerspectiveTransform(rect_src, rect_dst)

    The result’s a 3×3 warp matrix, defining methods to remodel from a skewed 3D perspective view to a 2D flat top-down view. To get this flat top-down view of our Sudoku grid, we will apply this attitude transformation to our authentic picture:

    warped = cv2.warpPerspective(img, warp_mat, (side_len, side_len))

    And voilà, we’ve got our completely sq. Sudoku grid!

    Remaining flat top-down view of Sudoku sq. after perspective transformation

    Conclusion

    On this undertaking we walked by a easy pipeline utilizing classical Laptop Imaginative and prescient strategies to extract Sudoku grids from photos. These strategies present a easy strategy to detect the bounds of the Sudoku grids. In fact as a consequence of its simplicity there are some limitations to how nicely this method generalizes to totally different settings and excessive environments resembling low gentle or arduous shadows. Utilizing a deep-learning primarily based method might make sense if the detection must generalize to an enormous quantity of various settings.

    Subsequent, a perspective transformation is used to get a flat top-down view of the grid. This picture can now be utilized in additional processing, resembling extracting the numbers within the grid and truly fixing the Sudoku. In a subsequent article we’ll look additional into these pure subsequent steps on this undertaking.

    Try the supply code of the undertaking beneath and let me know when you’ve got any questions or ideas on this undertaking. Till then, completely happy coding!


    For extra particulars and the complete implementation together with the code for the all of the animations and visualizations, try the supply code of this undertaking on my GitHub:

    https://github.com/trflorian/sudoku-extraction


    All visualizations on this submit had been created by the creator.



    Source link

    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleBuilding a Command-Line Quiz Application in R
    Next Article Elon Musk ska lansera betaversion av Grokipedia
    ProfitlyAI
    • Website

    Related Posts

    Artificial Intelligence

    Creating AI that matters | MIT News

    October 21, 2025
    Artificial Intelligence

    Scaling Recommender Transformers to a Billion Parameters

    October 21, 2025
    Artificial Intelligence

    Hidden Gems in NumPy: 7 Functions Every Data Scientist Should Know

    October 21, 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Top Posts

    OnePlus 13 kommer med omfattande AI-funktioner

    May 28, 2025

    Confusion Matrix Made Simple: Accuracy, Precision, Recall & F1-Score

    July 30, 2025

    Q&A: The climate impact of generative AI | MIT News

    April 7, 2025

    The 7 Best Free ChatGPT Detectors in 2025

    April 3, 2025

    Sam Altman and the whale

    August 11, 2025
    Categories
    • AI Technology
    • AI Tools & Technologies
    • Artificial Intelligence
    • Latest AI Innovations
    • Latest News
    Most Popular

    How To Build Effective Technical Guardrails for AI Applications

    October 6, 2025

    Graph Neural Networks Part 4: Teaching Models to Connect the Dots

    April 29, 2025

    Agentic AI 101: Starting Your Journey Building AI Agents

    May 2, 2025
    Our Picks

    Creating AI that matters | MIT News

    October 21, 2025

    Scaling Recommender Transformers to a Billion Parameters

    October 21, 2025

    Hidden Gems in NumPy: 7 Functions Every Data Scientist Should Know

    October 21, 2025
    Categories
    • AI Technology
    • AI Tools & Technologies
    • Artificial Intelligence
    • Latest AI Innovations
    • Latest News
    • Privacy Policy
    • Disclaimer
    • Terms and Conditions
    • About us
    • Contact us
    Copyright © 2025 ProfitlyAI All Rights Reserved.

    Type above and press Enter to search. Press Esc to cancel.