Skip to main content

QuadrilateralFitter is an efficient and easy-to-use Python library for fitting irregular quadrilaterals from irregular polygons or any noisy data.

Project description

QuadrilateralFitter

QuadrilateralFitter Logo QuadrilateralFitter is an efficient and easy-to-use library for fitting irregular quadrilaterals from polygons or point clouds.

QuadrilateralFitter helps you find that four corners polygon that best approximates your noisy data or detection, so you can apply further processing steps like: perspective correction or pattern matching, without worrying about noise or non-expected vertex.

Optimal Fitted Quadrilateral is the smallest area quadrilateral that contains all the points inside a given polygon.

Installation

You can install QuadrilateralFitter with pip:

pip install quadrilateral-fitter

Usage

There is only one line you need to use QuadrilateralFitter:

from quadrilateral_fitter import QuadrilateralFitter

# Fit an input polygon of N sides
fitted_quadrilateral = QuadrilateralFitter(polygon=your_noisy_polygon).fit()
Fitting Example 1   Fitting Example 2 

If your application can accept fitted quadrilateral to don't strictly include all points within input polygon, you can get the tighter quadrilateral shown as Initial Guess with:

fitted_quadrilateral = QuadrilateralFitter(polygon=your_noisy_polygon).tight_quadrilateral

API Reference

QuadrilateralFitter(polygon)

Initialize the QuadrilateralFitter instance..

  • polygon: np.ndarray | tuple | list | shapely.Polygon. List of the polygon coordinates. It must be a list of coordinates, in the format XY, shape (N, 2).

QuadrilateralFitter.fit(simplify_polygons_larger_than = 10):

  • simplify_polygons_larger_than: int | None. List of the polygon coordinates. It must be a list of coordinates, in the format XY, shape (N, 2). If a number is specified, the method will make a preliminar Douglas-Peucker simplification of the internally used Convex Hull if it has more than simplify_polygons_larger_than vertices. This will speed up the process, but may lead to a sub-optimal quadrilateral approximation. Default: 10.

Returns: tuple[tuple[float, float], tuple[float, float], tuple[float, float], tuple[float, float]]: A tuple containing the four XY coordinates of the fitted cuadrilateral. This quadrilateral will minimize the IoU (Intersection Over Union) with the input polygon, while containing all its points inside. If your use case can allow loosing points from the input polygon, you can read the QuadrilateralFitter.tight_polygon property to obtain a tighter quadrilateral.

Real Case Example

Let's simulate a real case scenario where we detect a noisy polygon from a form that we know should be a perfect rectangle (only deformed by perspective).

import numpy as np
import cv2

image = cv2.cvtColor(cv2.imread('./resources/input_sample.jpg'), cv2.COLOR_BGR2RGB)   

# Save the Ground Truth corners
true_corners = np.array([[50., 100.], [370., 0.], [421., 550.], [0., 614.], [50., 100.]], dtype=np.float32)

# Generate a simulated noisy detection
sides = [np.linspace([x1, y1], [x2, y2], 20) + np.random.normal(scale=10, size=(20, 2))
         for (x1, y1), (x2, y2) in zip(true_corners[:-1], true_corners[1:])]
noisy_corners = np.concatenate(sides, axis=0)

# To simplify, we will clip the corners to be within the image
noisy_corners[:, 0] = np.clip(noisy_corners[:, 0], a_min=0., a_max=image.shape[1])
noisy_corners[:, 1] = np.clip(noisy_corners[:, 1], a_min=0., a_max=image.shape[0])
Input Sample

And now, let's run QuadrilateralFitter to find the quadrilateral that best approximates our noisy detection (without leaving points outside).

from quadrilateral_fitter import QuadrilateralFitter

# Define the fitter (we want to keep it for reading internal variables later)
fitter = QuadrilateralFitter(polygon=noisy_corners)

# Get the fitted quadrilateral that contains all the points inside the input polygon
fitted_quadrilateral = np.array(fitter.fit(), dtype=np.float32)
# If you wanna to get a tighter mask, less likely to contain points outside the real quadrilateral, 
# but that cannot ensure to always contain all the points within the input polygon, you can use:
tight_quadrilateral = np.array(fitter.tight_quadrilateral, dtype=np.float32)

# To show the plot of the fitting process
fitter.plot()
Fitting Process     Fitted Quadrilateral 

Finally, for use cases like this, we could use fitted quadrilaterals to apply a perspective correction to the image, so we can get a visual insight of the results.

# Generate the destiny points for the perspective correction by adjusting it to a perfect rectangle
h, w = image.shape[:2]

for quadrilateral in (fitted_quadrilateral, tight_quadrilateral):
    # Cast it to a numpy for agile manipulation
    quadrilateral = np.array(quadrilateral, dtype=np.float32)

    # Get the bounding box of the fitted quadrilateral
    min_x, min_y = np.min(quadrilateral, axis=0)
    max_x, max_y = np.max(quadrilateral, axis=0)

    # Define the destiny points for the perspective correction
    destiny_points = np.array(((min_x, min_y), (max_x, min_y),
                               (max_x, max_y), (min_x, max_y)), dtype=np.float32)

    # Calculate the homography matrix from the quadrilateral to the rectangle
    homography_matrix, _ = cv2.findHomography(srcPoints=quadrilateral, dstPoints=rect_points)
    # Warp the image using the homography matrix
    warped_image = cv2.warpPerspective(src=image, M=homography_matrix, dsize=(w, h))
Input Segmentation Corrected Perspective Fitted Corrected Perspective Tight

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

quadrilateral_fitter-1.12.tar.gz (14.7 kB view details)

Uploaded Source

Built Distribution

quadrilateral_fitter-1.12-py3-none-any.whl (13.2 kB view details)

Uploaded Python 3

File details

Details for the file quadrilateral_fitter-1.12.tar.gz.

File metadata

  • Download URL: quadrilateral_fitter-1.12.tar.gz
  • Upload date:
  • Size: 14.7 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.1 CPython/3.12.5

File hashes

Hashes for quadrilateral_fitter-1.12.tar.gz
Algorithm Hash digest
SHA256 34b15b057c58cfd7ea63292227b1513c0b2a674c63ed7339c24847c780ac4656
MD5 9f3c43c518ecbaf83785f139d6715ba3
BLAKE2b-256 bb08b8dab6b34c319464c31a3b8f2e15f3150c96dd3a13274f4fe21d296555a1

See more details on using hashes here.

File details

Details for the file quadrilateral_fitter-1.12-py3-none-any.whl.

File metadata

File hashes

Hashes for quadrilateral_fitter-1.12-py3-none-any.whl
Algorithm Hash digest
SHA256 2de942db1af8c4517bb8849f5787749c5e564b9515573bf1eba988ad6a05eca8
MD5 5a6aa0408fe623363723b4189bd45e6e
BLAKE2b-256 38649cbc5397bdd3ec60b0120f79c6459733db6428c688a4a76d4cb2f36d6ed6

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page