⚡️ Speed up function `_equalize_cv` by 824% by KRRT7 · Pull Request #2361 · albumentations-team/albumentations

KRRT7 · 2025-02-26T23:00:26Z

📄 824% (8.24x) speedup for `_equalize_cv` in `albumentations/augmentations/functional.py`

⏱️ Runtime : 3.35 milliseconds → 363 microseconds (best of 2016 runs)

📝 Explanation and details

To improve the performance of the _equalize_cv function, we can focus on a few key areas. First, we should look at optimizing the loop operations, particularly avoiding redundant calculations and function calls. Let's go through the code and optimize it step by step.

Avoid Recomputing len(histogram) in Loop Condition.
- Pre-calculate len(histogram) to avoid recalculating it during each iteration of the loop.
Use Numpy Operations for Efficiency.
- Instead of looping through the histogram to find i, leverage numpy for finding the first non-zero entry.
- Avoid updating and checking variables inside the loop to reduce overhead.
Optimize the Lookup Table Computation.
- Use numpy's cumulative sum function to calculate the cumulative histogram more efficiently.
- Convert the cumulative values to the lookup table in a vectorized manner, reducing loop operations.

Key Changes.

Use of np.flatnonzero(): This efficiently locates the first non-zero entry in the histogram, simplifying the search loop to a single call.
Vectorized Operations for LUT: The computation of the cumulative sum and the creation of the lookup table (LUT) are handled using numpy's vectorized operations, which are typically faster and more efficient than explicit Python loops.

These optimizations focus on minimizing loop iterations and function calls, which should significantly improve the runtime efficiency of the function.

✅ Correctness verification report:

Test	Status
⚙️ Existing Unit Tests	🔘 None Found
🌀 Generated Regression Tests	✅ 22 Passed
⏪ Replay Tests	🔘 None Found
🔎 Concolic Coverage Tests	🔘 None Found
📊 Tests Coverage	100.0%

🌀 Generated Regression Tests Details

from __future__ import annotations

import cv2
import numpy as np
# imports
import pytest  # used for our unit tests
from albucore import clip, sz_lut
from albumentations.augmentations.functional import _equalize_cv

# unit tests

def test_full_image_equalization():
    # Test with a gradient image
    img = np.linspace(0, 255, 256, dtype=np.uint8).reshape(16, 16)
    expected = cv2.equalizeHist(img)
    codeflash_output = _equalize_cv(img)

def test_masked_equalization():
    # Test with a mask covering the central region
    img = np.linspace(0, 255, 256, dtype=np.uint8).reshape(16, 16)
    mask = np.zeros((16, 16), dtype=np.uint8)
    mask[4:12, 4:12] = 1
    codeflash_output = _equalize_cv(img, mask)

def test_uniform_image():
    # Test with a uniform image
    img = np.full((16, 16), 128, dtype=np.uint8)
    codeflash_output = _equalize_cv(img)
    expected = np.full((16, 16), 128, dtype=np.uint8)

def test_empty_mask():
    # Test with an empty mask
    img = np.linspace(0, 255, 256, dtype=np.uint8).reshape(16, 16)
    mask = np.zeros((16, 16), dtype=np.uint8)
    codeflash_output = _equalize_cv(img, mask)
    expected = np.zeros((16, 16), dtype=np.uint8)

def test_large_image():
    # Test with a large image
    img = np.random.randint(0, 256, (512, 512), dtype=np.uint8)
    codeflash_output = _equalize_cv(img)

def test_random_noise():
    # Test with random noise
    img = np.random.randint(0, 256, (16, 16), dtype=np.uint8)
    codeflash_output = _equalize_cv(img)

def test_boundary_values():
    # Test with boundary values
    img = np.array([[0, 255], [255, 0]], dtype=np.uint8)
    codeflash_output = _equalize_cv(img)

def test_invalid_input():
    # Test with an invalid input (non-grayscale image)
    img = np.random.randint(0, 256, (16, 16, 3), dtype=np.uint8)
    with pytest.raises(cv2.error):
        _equalize_cv(img)

def test_deterministic_output():
    # Test for deterministic output
    img = np.random.randint(0, 256, (16, 16), dtype=np.uint8)
    codeflash_output = _equalize_cv(img)
    codeflash_output = _equalize_cv(img)

def test_side_effects():
    # Test for side effects
    img = np.random.randint(0, 256, (16, 16), dtype=np.uint8)
    img_copy = img.copy()
    _equalize_cv(img)
# codeflash_output is used to check that the output of the original code is the same as that of the optimized code.

from __future__ import annotations

import cv2
import numpy as np
# imports
import pytest  # used for our unit tests
from albucore import clip, sz_lut
from albumentations.augmentations.functional import _equalize_cv

# unit tests

def test_grayscale_no_mask():
    # Test a simple 8x8 image with random values
    img = np.random.randint(0, 256, (8, 8), dtype=np.uint8)
    codeflash_output = _equalize_cv(img)

def test_uniform_image_no_mask():
    # Test a uniform image where all pixels have the same intensity
    img = np.full((8, 8), 128, dtype=np.uint8)
    codeflash_output = _equalize_cv(img)

def test_gradient_image_no_mask():
    # Test an image with a linear gradient
    img = np.tile(np.arange(256, dtype=np.uint8), (256, 1))
    codeflash_output = _equalize_cv(img)

def test_grayscale_with_mask():
    # Test a random 8x8 image with a mask selecting a rectangular region
    img = np.random.randint(0, 256, (8, 8), dtype=np.uint8)
    mask = np.zeros((8, 8), dtype=np.uint8)
    mask[2:6, 2:6] = 1
    codeflash_output = _equalize_cv(img, mask)

def test_empty_image():
    # Test an image with zero width or height
    img = np.empty((0, 8), dtype=np.uint8)
    codeflash_output = _equalize_cv(img)

def test_extreme_values():
    # Test an image with minimum and maximum intensity values only
    img = np.zeros((8, 8), dtype=np.uint8)
    img[::2] = 255
    codeflash_output = _equalize_cv(img)

def test_full_zero_mask():
    # Test a mask that is entirely zeros
    img = np.random.randint(0, 256, (8, 8), dtype=np.uint8)
    mask = np.zeros((8, 8), dtype=np.uint8)
    codeflash_output = _equalize_cv(img, mask)

def test_full_one_mask():
    # Test a mask that is entirely ones
    img = np.random.randint(0, 256, (8, 8), dtype=np.uint8)
    mask = np.ones((8, 8), dtype=np.uint8)
    codeflash_output = _equalize_cv(img, mask)

def test_large_image():
    # Test a large image to assess performance
    img = np.random.randint(0, 256, (512, 512), dtype=np.uint8)
    codeflash_output = _equalize_cv(img)

def test_invalid_mask_size():
    # Test a mask with a different size than the image
    img = np.random.randint(0, 256, (8, 8), dtype=np.uint8)
    mask = np.ones((4, 4), dtype=np.uint8)
    with pytest.raises(Exception):
        _equalize_cv(img, mask)

def test_non_binary_mask():
    # Test a mask with non-binary values
    img = np.random.randint(0, 256, (8, 8), dtype=np.uint8)
    mask = np.random.randint(0, 256, (8, 8), dtype=np.uint8)
    codeflash_output = _equalize_cv(img, mask)
# codeflash_output is used to check that the output of the original code is the same as that of the optimized code.

Summary by Sourcery

Optimizes the _equalize_cv function for improved performance by leveraging NumPy operations to minimize loop iterations and function calls.

Enhancements:

Optimized the _equalize_cv function in albumentations/augmentations/functional.py by using NumPy operations to avoid redundant calculations and function calls, resulting in an 824% speedup.

Tests:

Added regression tests to ensure the correctness of the optimized _equalize_cv function.

To improve the performance of the `_equalize_cv` function, we can focus on a few key areas. First, we should look at optimizing the loop operations, particularly avoiding redundant calculations and function calls. Let's go through the code and optimize it step by step. 1. **Avoid Recomputing `len(histogram)` in Loop Condition**. - Pre-calculate `len(histogram)` to avoid recalculating it during each iteration of the loop. 2. **Use Numpy Operations for Efficiency**. - Instead of looping through the `histogram` to find `i`, leverage numpy for finding the first non-zero entry. - Avoid updating and checking variables inside the loop to reduce overhead. 3. **Optimize the Lookup Table Computation**. - Use numpy's cumulative sum function to calculate the cumulative histogram more efficiently. - Convert the cumulative values to the lookup table in a vectorized manner, reducing loop operations. ### Key Changes. - **Use of `np.flatnonzero()`**: This efficiently locates the first non-zero entry in the `histogram`, simplifying the search loop to a single call. - **Vectorized Operations for LUT**: The computation of the cumulative sum and the creation of the lookup table (LUT) are handled using numpy's vectorized operations, which are typically faster and more efficient than explicit Python loops. These optimizations focus on minimizing loop iterations and function calls, which should significantly improve the runtime efficiency of the function.

sourcery-ai · 2025-02-26T23:00:29Z

Reviewer's Guide by Sourcery

This pull request significantly improves the performance of the _equalize_cv function by optimizing the histogram processing and lookup table generation. It replaces iterative calculations with vectorized numpy operations, resulting in a substantial speedup.

Sequence diagram for optimized _equalize_cv function

sequenceDiagram
  participant Img as Image
  participant cv2
  participant np as numpy
  participant sz_lut

  Img->>cv2: calcHist(img, mask)
  cv2-->>Img: histogram
  Img->>np: flatnonzero(histogram)
  np-->>Img: i (first non-zero index)
  Img->>np: cumsum(histogram)
  np-->>Img: cumsum_histogram
  Img->>np: clip(((cumsum_histogram - cumsum_histogram[i]) * scale).round(), 0, 255).astype(np.uint8)
  np-->>Img: lut
  Img->>sz_lut: sz_lut(img, lut, inplace=True)
  sz_lut-->>Img: Equalized image

File-Level Changes

Change	Details	Files
Optimized the calculation of the starting index for histogram equalization.	Replaced the loop that finds the first non-zero element in the histogram with `np.flatnonzero()` for improved efficiency.	`albumentations/augmentations/functional.py`
Optimized the generation of the lookup table (LUT) for histogram equalization.	Replaced the iterative cumulative sum calculation with `np.cumsum()` for vectorized computation. Applied a vectorized approach to scale and clip the cumulative histogram values to create the LUT.	`albumentations/augmentations/functional.py`

Tips and commands

Interacting with Sourcery

Trigger a new review: Comment @sourcery-ai review on the pull request.
Continue discussions: Reply directly to Sourcery's review comments.
Generate a GitHub issue from a review comment: Ask Sourcery to create an
issue from a review comment by replying to it. You can also reply to a
review comment with @sourcery-ai issue to create an issue from it.
Generate a pull request title: Write @sourcery-ai anywhere in the pull
request title to generate a title at any time. You can also comment
@sourcery-ai title on the pull request to (re-)generate the title at any time.
Generate a pull request summary: Write @sourcery-ai summary anywhere in
the pull request body to generate a PR summary at any time exactly where you
want it. You can also comment @sourcery-ai summary on the pull request to
(re-)generate the summary at any time.
Generate reviewer's guide: Comment @sourcery-ai guide on the pull
request to (re-)generate the reviewer's guide at any time.
Resolve all Sourcery comments: Comment @sourcery-ai resolve on the
pull request to resolve all Sourcery comments. Useful if you've already
addressed all the comments and don't want to see them anymore.
Dismiss all Sourcery reviews: Comment @sourcery-ai dismiss on the pull
request to dismiss all existing Sourcery reviews. Especially useful if you
want to start fresh with a new review - don't forget to comment
@sourcery-ai review to trigger a new review!
Generate a plan of action for an issue: Comment @sourcery-ai plan on
an issue to generate a plan of action for it.

Customizing Your Experience

Access your dashboard to:

Enable or disable review features such as the Sourcery-generated pull request
summary, the reviewer's guide, and others.
Change the review language.
Add, remove or edit custom review instructions.
Adjust other review settings.

Getting Help

Contact our support team for questions or feedback.
Visit our documentation for detailed guides and information.
Keep in touch with the Sourcery team by following us on X/Twitter, LinkedIn or GitHub.

sourcery-ai

Hey @KRRT7 - I've reviewed your changes - here's some feedback:

Overall Comments:

It would be good to add a unit test that compares the output of the original and optimized functions.

Here's what I looked at during the review

🟢 General issues: all looks good
🟢 Security: all looks good
🟢 Testing: all looks good
🟢 Complexity: all looks good
🟢 Documentation: all looks good

Sourcery is free for open source - if you like our reviews please consider sharing them ✨

_{Help me be more useful! Please click 👍 or 👎 on each comment and I'll use the feedback to improve your reviews.}

sourcery-ai bot reviewed Feb 26, 2025

View reviewed changes

ternaus merged commit 4f8a4e4 into albumentations-team:main Feb 26, 2025

KRRT7 deleted the codeflash/optimize-_equalize_cv-m698ftyi branch March 4, 2025 02:22

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

⚡️ Speed up function `_equalize_cv` by 824%#2361

⚡️ Speed up function `_equalize_cv` by 824%#2361
ternaus merged 1 commit intoalbumentations-team:mainfrom
KRRT7:codeflash/optimize-_equalize_cv-m698ftyi

KRRT7 commented Feb 26, 2025 •

edited by sourcery-ai bot

Loading

Uh oh!

sourcery-ai bot commented Feb 26, 2025 •

edited

Loading

Interacting with Sourcery

Customizing Your Experience

Getting Help

Uh oh!

sourcery-ai bot left a comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Uh oh!

Conversation

KRRT7 commented Feb 26, 2025 • edited by sourcery-ai bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

📄 824% (8.24x) speedup for _equalize_cv in albumentations/augmentations/functional.py

Key Changes.

Summary by Sourcery

Uh oh!

sourcery-ai bot commented Feb 26, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Reviewer's Guide by Sourcery

Sequence diagram for optimized _equalize_cv function

File-Level Changes

Interacting with Sourcery

Customizing Your Experience

Getting Help

Uh oh!

sourcery-ai bot left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

KRRT7 commented Feb 26, 2025 •

edited by sourcery-ai bot

Loading

📄 824% (8.24x) speedup for `_equalize_cv` in `albumentations/augmentations/functional.py`

sourcery-ai bot commented Feb 26, 2025 •

edited

Loading