Floyd-Steinberg Dithering

[Amateurprofi]

Zitat von himitsu:

Delphi-Quellcode:

var R: TRect;

with R do
  Width := Right - Left + 1;

Also ich fand es witzig, als so ein Code urplötzlich nichts mehr machte, also nicht mehr die Breite der Form zu setzen,
weil TRect plötzlich ein Property Width bekommen hatte und Dieses dann eben nicht mehr das Width der Form war.

PS: Inline-Variablen, wenn es unbedingt sein muß.

Ja, genau das ist mir mal mit einem Uralt-Programm passiert, das (neu kompiliert) auf einmal nicht mehr lief.
Hab damals ziemlich lange gebraucht, um zu begreifen, woran es lag.

[Amateurprofi]

Zitat von Uwe Raabe:

OT: Wie kommt man eigentlich auf die Idee, einen 15 Jahre alten Thread wieder aufleben zu lassen? Insbesondere, da die letzte Aktivität des Posters mittlerweile auch schon fast 11 Jahre zurück liegt.

Weil ich auf der Suche nach einem Floyd-Steinberg Algo auf den Thread gestoßen bin und wirklich happy war, als ich den bei shmia fand.
Ich hätte das ja auch als neuen Thread, ohne Bezug auf shmia, posten können, aber ich schmücke mich nicht gern mit fremden Federn.
Übrigens: Die Pyramiden bei Gizeh sind etwas älter als 15 Jahre und werden trotzdem gern und oft besucht.

[Amateurprofi]

Zitat von Kas Ob.:

Excellent work.

I have few suggestion:
1) Switch from using Integer to NativeUInt or NativeInt, this will pay in x64, as the compiler will not have to insert resizing instructions like movzx and will have the ability to use full register operation.
2) Replace that EnsureRange with simple old fashion if-statement, saving a needless branch.
3) I wouldn't trust the compiler to generate fast div every time when the division is by 2^n, proof this by replacing them with shr n, so div 16 can be shr 4.
4) This is the meat of this and i think it should pay on low cache CPU's or big images or very busy CPU, instead of getting the last line which have the index 0 then go backward "PP:=Bmp.ScanLine[0];" replace with getting the first line and move forward, also for X there is no point of walking backward, see, with huge images, and walking backward the cache lines will continuously be read in backward causing violation and request to update, while the CPU request its cache lines in bulk forward most the time, so accessing the memory backward with thrash the cache and waste time and cycles waiting for memory.

Zitat:

3) I wouldn't trust the compiler to generate fast div every time when the division is by 2^n, proof this by replacing them with shr n, so div 16 can be shr 4.

No!
shr with negative numbers?
The compiler converts "Div 16" to "sar 4".

[himitsu]

Zitat:

Regelwerk

Ja, teilweise wird es verboten,

aber im Grunde ist es einfach ein "es gibt massenhaft Probleme damit, von nervt beim Debuggen, über CodeInsight/Refactoring dreht durch, bis zu Programmfehler, weil sich was geändert hat .... drum sollte man es besser garnicht erst verwenden"

Zitat:

with shr n, so div 16 can be shr 4.

only for unsigned integers

[Amateurprofi]

[QUOTE=Amateurprofi;1528396]

Zitat von Kas Ob.:

Excellent work.

I have few suggestion:
1) Switch from using Integer to NativeUInt or NativeInt, this will pay in x64, as the compiler will not have to insert resizing instructions like movzx and will have the ability to use full register operation.
2) Replace that EnsureRange with simple old fashion if-statement, saving a needless branch.
3) I wouldn't trust the compiler to generate fast div every time when the division is by 2^n, proof this by replacing them with shr n, so div 16 can be shr 4.
4) This is the meat of this and i think it should pay on low cache CPU's or big images or very busy CPU, instead of getting the last line which have the index 0 then go backward "PP:=Bmp.ScanLine[0];" replace with getting the first line and move forward, also for X there is no point of walking backward, see, with huge images, and walking backward the cache lines will continuously be read in backward causing violation and request to update, while the CPU request its cache lines in bulk forward most the time, so accessing the memory backward with thrash the cache and waste time and cycles waiting for memory.

Have tested your suggestions.
1) NativeInt instead of Integers
Doubles the used time.
2) Replacing EnsureRange bei If then ..,
Adds another few ms
3) shr instead of Div 16
Commented earlier
4) Starting with the Bottom Line
Not tested, would expect advantages
4) X forward
Not tested would expect disadvantages (see the "if X<>..." in the X-Loop)

The measured runtimes
1339 With Integers
2559 With NativeInts
2606 EnsureRange replaced by If-Then

[Kas Ob.]

Hi for all,
Please bare a little with me, i mean really don't take my calling the Delphi Compiler as an offense toward anyone, it is just i know it, i used to be and still earning my bread from optimizing old and new code, i know the compiler very intimately to call it a fucking centuries old brick.

I will explain just this piece of code, and if you want to expand on it, but first and foremost please, at least consider your knowledge of the code generated by Delphi is wrong(outdated or naively trusting) or unoptimized (inefficient) and will go from there to proof a contradiction, how about that ?.. it is my best method as mathematician by education.

so many agreed on div 16 is always shr 4 or to be more concise should be sar 4, i agree and i know that the compiler wrongly do it for unsigned integers, but this is not the case, as i was talking about that specific case at hand, may be it is my mistake may to not wrote an essay for each line i wrote.

So here a proof that the compiler doesn't use sar 4 or shr 4 for div 16, the proof is just look at x64 version of it !!

try this function in the above optimized version

Code:

PROCEDURE SetPixel(XOffset,YOffset,Factor:NativeInt);
var AP:TPBGR;
begin
   // XOffset=Horizontaler Offset in Pixel
   // YOffset=Vertikaler Offset in Bytes
   AP:=P;
   Inc(AP,XOffset);
   Inc(NativeInt(AP),YOffset);
   with AP^, Delta do begin
      Blue:=EnsureRange(Blue+B*Factor shr 4,0,255);
      Green:=EnsureRange(Green+G*Factor shr 4,0,255);
      Red:=EnsureRange(Red+R*Factor shr 4,0,255);
   end;
end;

My speed shows that it is faster by 18% in Win32 and 29% on Win64 !! do it please, it is not slower by 200%, and these values as positive so no problem here.
also if you look at the generated assembly code, then this is it


Also try this

Code:

  procedure SetPixel(XOffset, YOffset, Factor: NativeInt);
  var
    AP: TPBGR;
    v: NativeInt;
  begin
    AP := P;
    Inc(AP, XOffset);
    Inc(NativeInt(AP), YOffset);
    with AP^, Delta do
    begin
      v := Blue + B * Factor shr 4;
      if v < 0 then
        Blue := 0
      else if v > 255 then
        Blue := 255
      else
        Blue := v;

      v := Green + G * Factor shr 4;
      if v < 0 then
        Green := 0
      else if v > 255 then
        Green := 255
      else
        Green := v;

      v := Red + R * Factor shr 4;
      if v < 0 then
        Red := 0
      else if v > 255 then
        Red := 255
      else
        Red := v;
    end;
  end;

The above function makes the whole process around double the speed, for both platform .

and again not saying that i know it all, i do mistakes, but not in this case, would love to be proven wrong, but with factual code done right not with you assumptions based on something you didn't see for sure.

My test is attached here FloydSteinberg.zip and hope it is working unlike the above attached project as it is empty.

As for "with" the compiler might fail to generate nice assembly and will revert to shuffle the data and access them continuously on the stack introducing unneeded memory access, this happen with complex loops also, with "with" it in many case will resolve the pointer and reused it from a register, alas it seems no gain in the above mentioned function, but once the function have few more local variables and it will go 90s turbo pascal mode specially in x64 platforms, i don't have the mood to sit and tweak such case for you now, but the effect is there.

ps re-reading before posting this, i sound retarded and offended, and i am sorry for that, i don't mean to offend anyone and never meant to, just had very bad experience from an neighbor forum and trying to be triggered by personal sentences.

[Kas Ob.]

Forgot to attach a screenshot of my result


May be not in everyone interest to notice that, but do you see the consistency in the result, or the closeness of the result, this show the relax and the ability of the cache on CPU level, just by removing the EnsureRange branching for each pixel 3 times.

[skybibo]

Ich glaube das wir so zwar einen sehr schnellen Algorithmus haben, aber nicht das Ergebnis bekommen, dass wir erwarten. Es wird für den Quell und Zielbereich die selbe Bitmap verwendet, daher bezieht sich die Berechnung zum Teil auf Pixel, die zuvor schon geändert wurden, anstatt auf die Original Daten.

Daher würde ich eine Zweite Bitmap für das Ergebnis verwenden. Der nächste Schritt wäre dann die Verwendung von TParallel.For um noch schneller zu werden. Optimal wäre dann als nächstes die Verwendung von Cuda oder OpenCL.

[Kas Ob.]

Zitat von skybibo:

Ich glaube das wir so zwar einen sehr schnellen Algorithmus haben, aber nicht das Ergebnis bekommen, dass wir erwarten. Es wird für den Quell und Zielbereich die selbe Bitmap verwendet, daher bezieht sich die Berechnung zum Teil auf Pixel, die zuvor schon geändert wurden, anstatt auf die Original Daten.

Yes, and thank you, i see my mistake, though the difference should not negate the gain in performance from using removing EnsureRange and replacing shr 4 with div on x64.

The code can be rearranged little more.

[himitsu]

Zitat von skybibo:

Ich glaube das wir so zwar einen sehr schnellen Algorithmus haben, aber nicht das Ergebnis bekommen, dass wir erwarten. Es wird für den Quell und Zielbereich die selbe Bitmap verwendet, daher bezieht sich die Berechnung zum Teil auf Pixel, die zuvor schon geändert wurden, anstatt auf die Original Daten.

Daher würde ich eine Zweite Bitmap für das Ergebnis verwenden. Der nächste Schritt wäre dann die Verwendung von TParallel.For um noch schneller zu werden. Optimal wäre dann als nächstes die Verwendung von Cuda oder OpenCL.

Das ist hier kein Problem, da hier für jedes Pixel extra nicht die umgebenden Pixel betrachtet werden (wo bereits bearbeitete enthalten wären),
sondern ausschließlich nur nachfolgende Pixel "leicht geändert" werden, welche später dran kommen.

https://youtu.be/PyRrgjwpzYE?si=mG1QEo_MAYzSqJXW&t=444

Zitat:

Threads, TParallel.For usw.

Problem ist hier auch, dass es sich nicht parallelisieren lässt, da es immer Überschneidungen gibt, außer du hast irgendwo 100% schwarze bzw. weiße Pixel, welche keinen Fehler verursachen.
Denn nur nach solchen Zeilen (oder Spalten) kannst du "neu" beginnen, ohne dass die nachfolgende Zeile einen Einfluß hat.

Würden der "Fehler" nur auf nachfolgene in der eigenen Zeile verteilt, dann gäbe es zwischen den Zeilen keine Beziehung und du könntest es parallelisieren.
Ausnahme: man teilt das Bild vorher in Blöcke und berechnet jeden Block für sich, aber da kann es gerade "kanten" im Bild geben, wo sich optisch sichtbar die Verteilung ändert.



JA, es lässt sich "theoretisch" parallelisieren, also die nächste Zeile lässt sich schon berechnen, während die vorhergehende Zeile noch arbeitet (Zeilen übersrpingen geht nicht),
aber der Aufwand das zu synchronisieren frißt bestimmt die Ersparnis auf,
denn es muß immer 2 Pixel hinter der jeweils vorherigen Zeile bleiben, weil dort da dann die Fehlerwerte bereits fest stehen.
Je Zeile ein Thread würde es sich dann von der Ecke links-oben nach rechts-unten bewegen.
Außerdem würden dann die Threads gegenseitig in gleichen Speicherblöcken arbeiten, was dem Cache der CPU komplett entgegen wirkt und es nur noch bremst.