Global histogram equalisation is non-deterministic

[nullpainter]

Prerequisites

• I have written a descriptive issue title
• I have verified that I am running the latest version of ImageSharp
• I have verified if the problem exist in both DEBUG and RELEASE mode
• I have searched open and closed issues to ensure it has not already been reported

Description

As per discussion #1413, applying the default global histogram on an image produces different results on repeated runs of the same image.

Steps to Reproduce

I have created a repro which demonstrates this issue. It loads an image, performs histogram equalisation a number of times and reports on the percentage of pixel differences between repeated runs.

Sample output:

Run #1: 56.93% different pixels to reference
Run #2: 54.81% different pixels to reference
Run #3: 61.85% different pixels to reference
Run #4: 61.83% different pixels to reference

Note that adaptive sliding window and adaptive tile interpolation do not exhibit this behaviour:

Run #1: identical to reference
Run #2: identical to reference
Run #3: identical to reference
Run #4: identical to reference

System Configuration

• ImageSharp version: 1.0.1
• Environment (Operating system, version and so on): Windows 10
• .NET Framework version: .NET Core 5 preview, compiled with .NET Core 3.1

[antonfirsov]

Thanks!

Quoting @tocsoft from an internal discussion:

just had a quick look at the histogram code looks like we are manipulating a shared buffer in parallel in GrayscaleLevelsRowOperation the increment isn't interlocked so from what i can tell there is a chance that some of the increment operations could be lost...wonder if we have the issue if Parallelism is disabled.

Any further investigation, or other any form of community help is welcome as always! :)

[JimBobSquarePants]

Yep, reviewed the histogram generation code. It shouldn't be parallel.

[brianpopow]

i see the issue now. Its during the histogram calculation. We can use Interlocked.Increment here and still do it in parallel.

[brianpopow]

closed via #1418

Thanks for reporting this @nullpainter