Skalowanie obrazu (interpolacja, upscaling)

Witam.

Staram się sklecić w miarę wydajny ale też szybki algorytm do skalowania bitmap.

W przypadku powiększania (upscaling) mój wybór padł na interpolację dwuliniową (bilinear), bo po prostu daje niezłe efekty niewielkim kosztem. Nie aż tak dobre jak bicubic, ale przy tym nie jest aż tak wymagająca obliczeniowo. Wydaję mi się, że wszystko robię dobrze, ale jedna rzecz nie daje mi spokoju, więc wyjaśnię po krótce o co chodzi (w przykładzie posłużę się "obrazem" 1D, złożonym z poziomej linii - tak dla ułatwienia).

Załóżmy, że mam obraz o szerokości 5, a chciałbym go przeskalować do szerokości 7. Najpierw muszę sobie wyliczyć współrzędne nowych pikseli względem tych pierwotnych.

R = nowa wielkość / oryginalna wielkość = 5/7 = 0,7142
Współrzędna X piksela z obrazu końcowego na obrazie pierwotnym = Współrzędna X piksela obrazu końcowego * R

Czyli kolejno:

X(0) = 0 * R = 0 (kopia piksela 0 z obrazu pierwotnego)
X(1) = 1 * R = 0,7142 (sub-piksel interpolowany pomiędzy pikselem 0 i 1)
X(2) = 2 * R = 1,4284 (sub-piksel interpolowany pomiędzy pikselem 1 i 2)
X(3) = 3 * R = 2,1426 (sub-piksel interpolowany pomiędzy pikselem 2 i 3)
X(4) = 4 * R = 2,8568 (sub-piksel interpolowany pomiędzy pikselem 2 i 3)
X(5) = 5 * R = 3,571 (sub-piksel interpolowany pomiędzy pikselem 3 i 4)
X(6) = 6 * R = 4,2852 (sub-piksel interpolowany pomiędzy pikselem 4 i 5)

Z powyższego wychodzi, że pierwszy piksel końcowego obrazu zawsze jest po prostu kopią pierwszego piksela z obrazu pierwotnego (bo cokolwiek pomnożone przez zero, zawsze da zero), natomiast wszystkie inne piksele są sub-pikselami leżącymi gdzieś na granicy dwóch pikseli pierwotnego obrazu. Tak powinno być? To niby nic wielkiego ale jakoś mi ten pierwszy piksel nie pasuje.

Crow napisał(a):

jakoś mi ten pierwszy piksel nie pasuje.

I slusznie. Czemu obliczenie pierwszego piksela mialoby byc inne niz ostatniego? To powinno byc symetryczne. Np. obrocenie obrazu + skalowanie + obrocenie powinno dac taki sam wynk jak samo skalowanie.
Gotowe implementacje nietrudno podejzec np. w OpenCV (tyle ze tam jest oczywicie bardziej zlozone, chocby dlatego ze uwzgledniane sa obydwa wymiary, ale sa tez rozne implementacje w zaleznosci na co jest optymalizowane, i sa dodatkowe optymalizacje dla przypadkow szczegolnych - ogolnie przesadnie czytelne to to nie jest).

Wydaje mi się (ale teraz zmyślam, nie żebym się znał) że liczysz interpolację dla lewego górnego rogu każdego piksela, dlatego lewy górny piksel obrazu staje się uprzywilejowany.
Powinieneś raczej liczyć wartości dla środka każdego piksela.

Może rozrysuj to sobie na kartce w kratkę i sensowne wzory przyjdą do głowy.

Tak siedzę nad tym i ciągle mi coś nie pasuje. Popatrzcie na taki przykład:

5 zwiększamy do 11 --> 5 / 11 = R = 0,455

No i pozycja przyrostowo wychodzi tak:

 0 * R = 0,000
 1 * R = 0,455
 2 * R = 0,909
 3 * R = 1,364
 4 * R = 1,818
 5 * R = 2,273
 6 * R = 2,727
 7 * R = 3,182
 8 * R = 3,636
 9 * R = 4,091
10 * R = 4,545
11 * R = 5,000

Tylko które piksele mam teraz wykorzystać i jak?

Po pierwsze, niezłym pomysłem będzie chyba skopiowanie pierwszego i ostatniego piksela obrazu pierwotnego i umieszczenie ich na pozycjach 0 i 10 obrazu końcowego.
Po drugie, powinienem chyba uwzględnić zakres od 1 do 11 zamiast od 0 do 10 (bo to pozwala wykorzystać pełen zakres obrazu), a potem po prostu zmniejszać koordynat piksela o 1, np.:

10 * R = 4,545 //piksel obrazu końcowego powinien leżeć pomiędzy pikselami 4 i 5 obrazu pierwotnego, a numerując od 0
                 (zmniejszając indeksy o 1), między pikselami 3 i 4.

Do tego miejsca wszystko się niby składa, tylko co zrobić z pikselami, które leżą PRZED pierwszym pikselem obrazu pierwotnego? Bo skoro 1,364 będzie leżał pomiędzy 1 i 2 (a po dopasowaniu indeksów, między 0 i 1), to gdzie będzie leżał 0,909? Wychodziło by na to, że między pikselem -1 i 0, ale przecież to niemożliwe, bo piksela -1 nie ma. Czy to zatem oznacza, że powinienem w takich przypadkach po prostu skopiować wartość piksela 0? Nie wydaje mi się to dobrym pomysłem, bo przecież w wielu przypadkach wytworzy to jednolity blok skopiowanych pikseli (jak przy metodzie najbliższego sąsiada). Może lepiej przeskalować pierwszy piksel obrazu pierwotnego przez tą wartość zamiast go kopiować? Czyli np.:

0,909 * [R:123, G:78, B:198]

A może powinienem ekstrapolować?

Jakieś pomysły? Proszę o jakąś podpowiedź, bo mnie to psychicznie wykańcza :). W internecie jest trochę przykładów odnośnie tej metody skalowania, ale jakoś wszystkie pomijają ten problem, albo rzucają lakonicznie i zupełnie bezużyteczne: "No, to teraz rzutuj sobie piksele nowego obrazu na pierwotny obraz i masz współrzędne...".

@Crow:

Po pierwsze, niezłym pomysłem będzie chyba skopiowanie pierwszego i ostatniego piksela obrazu pierwotnego i umieszczenie ich na pozycjach 0 i 10 obrazu końcowego.

Wtedy część pikseli (wewnętrzne) interpolujesz, a części (najbardziej zewnętrznych) nie, bo zwyczajnie je skopiujesz. Ale to nie naprawi "asymetrii" całego przedsięwzięcia, bo interpolowane piksele nadal będą miały tendencję by ciążyć w górną lewą stronę :P

Moim zdaniem jedynie niepotrzebnie skomplikujesz - a potencjalnie mógłbyś dodatkowo np. popsuć lekko gradienty przy brzegach obrazu.

Nie mógłbyś na przykład do współrzędnych dodawać 0,5R, by interpolacja była symetryczna i niezależna od obrotów / odbić? ;)

@Crow:

Czyli np. X(2) = (R * 2) + (R * 0,5)? Ale w jaki sposób ma mi to pomóc? :). Bo np. (R * 1) + (R * 0,5) da mi 0,682, czyli dalej będzie to leżało na lewo od piksela 0, czyli pomiędzy -1 i 0.

Jakim sposobem wyszło Ci 0,682 między -1 a 0? Nie brzmi to sensownie ;)

Zmierzam do tego, że próbkując w podany przez siebie sposób wprowadzasz pewną asymetrię:

• nowy pierwszy piksel będzie wierną kopią starszego pierwszego piksela
• nowy ostatni piksel będzie... sub-pikselem między dwoma innymi

Z czego wynika, że wszystkie kolejne piksele nowego obrazu będą przesunięte o pewien ułamek piksela względem takiego, który byłby próbkowany "symetrycznie".

Moja sugestia miała na celu doprowadzenie do tego, by próbkowanie było symetryczne tj. by wykluczyć "faworyzowanie" jednej ze stron. Ale teraz widzę, że właściwie niewiele by to dało, bo dalej byłoby źle).

Problem tkwi tutaj:

X(6) = 6 * R = 4,2852 (sub-piksel interpolowany pomiędzy pikselem 4 i 5)

Pierwotny obraz miał 5 pikseli szerokości, zatem piksel 5 nawet nie istnieje :) Co gorsza asymetria nadal będzie występować, tyle że na korzyść drugiej krawędzi. Żeby to zilustrować, rozważ trochę ładniejszy współczynnik R=0,5 i upscaling np. z 4px do 8px:

X(0) = 0 * R  = 0 (piksel 0)
X(1) = 1 * R = 0.5 (pół na pół z pikseli 0 i 1)
X(2) = 2 * R = 1 (piksel 1)
... itd
X(6) = 6 * R = 3 (piksel 3)
X(7) = 7 * R = 3.5 (gdzieś na prawo od piksela 3)

Jak widzisz, w takiej sytuacji po upscalingu coś się nie zgadza - nie ma już z czego interpolować, możesz najwyżej wziąć wartość starego piksela 3 jako kolor nowego piksela 7 - piksel 3 jako jedyny wystąpi po upscalingu dwa razy. Tego raczej nie chcemy.

Rzecz w tym, że do obliczania współczynnika R nie powinieneś brać szerokości w pikselach przed i po upscalingu, ponieważ interpolując przypisujesz pikselom pewne punkty (odpowiadające ich współrzędnym) i szukasz wartości (kolorów) w nowych punktach leżących gdzieś pomiędzy nimi i faktyczna szerokość wynosi N - 1. Zatem dla obrazka o szerokości 5px powinieneś tak naprawdę przyjąć szerokość 4, dla obrazka o szerokości 11px wartość 10 itd.

Sprawdźmy raz jeszcze na przykładzie z upscalingiem z 5px do 11px:

R = (5 - 1)/(11 - 1) = 4/10 = 0.4

X(0) = 0 * R  = 0
X(1) = 1 * R = 0.4
X(2) = 2 * R = 0.8
...
X(8) = 8 * R = 3.2
X(9) = 9 * R = 3.6
X(10) = 10 * R = 4

Teraz skrajne piksele się pokrywają, a próbkowanie kolorów nie będzie "ciążyć" w żadną stronę ;)

@superdurszlak:

superdurszlak napisał(a):

Jakim sposobem wyszło Ci 0,682 między -1 a 0? Nie brzmi to sensownie ;)

No bo jak ustaliliśmy, każdy koordynat trzeba przesunąć o -1 :). Bo R * 11 = 5, a wiemy przecież, że przy indeksowaniu od 0 ostatnim pikselem nie jest 5, tylko 4. Dlatego też wszystko co znajduje się w zakresie 0-1 (obliczone ze wzoru R * Indeks nowego piksela), leży tak naprawdę na lewo od pierwszego piksela pierwotnego, czyli w zakresie od -1 do 0.

Rzecz w tym, że do obliczania współczynnika R nie powinieneś brać szerokości w pikselach przed i po upscalingu, ponieważ interpolując przypisujesz pikselom pewne punkty (odpowiadające ich współrzędnym) i szukasz wartości (kolorów) w nowych punktach leżących gdzieś pomiędzy nimi i faktyczna szerokość wynosi N - 1. Zatem dla obrazka o szerokości 5px powinieneś tak naprawdę przyjąć szerokość 4, dla obrazka o szerokości 11px wartość 10 itd.

Sprawdźmy raz jeszcze na przykładzie z upscalingiem z 5px do 11px:

R = (5 - 1)/(11 - 1) = 4/10 = 0.4

X(0) = 0 * R  = 0
X(1) = 1 * R = 0.4
X(2) = 2 * R = 0.8
...
X(8) = 8 * R = 3.2
X(9) = 9 * R = 3.6
X(10) = 10 * R = 4

Teraz skrajne piksele się pokrywają, a próbkowanie kolorów nie będzie "ciążyć" w żadną stronę ;)

Ma to z pewnością jakiś sens, ale nadal pierwszy i ostatni piksel będą po prostu skopiowane. Nie wiem czy stanowi to problem, po prostu nie jestem pewien, czy tak się powinno robić :).

W internecie znalazłem np. coś takiego, ale nie wiem jak miałoby mi to pomóc ;/.

https://answers.opencv.org/question/208969/theory-behind-center-of-top-left-pixel-considered-as-0-0/

Crow napisał(a):

@superdurszlak:

superdurszlak napisał(a):

Jakim sposobem wyszło Ci 0,682 między -1 a 0? Nie brzmi to sensownie ;)

No bo jak ustaliliśmy, każdy koordynat trzeba przesunąć o -1 :). Bo R * 11 = 5, a wiemy przecież, że przy indeksowaniu od 0 ostatnim pikselem nie jest 5, tylko 4. Dlatego też wszystko co znajduje się w zakresie 0-1 (obliczone ze wzoru R * Indeks nowego piksela), leży tak naprawdę na lewo od pierwszego piksela pierwotnego, czyli w zakresie od -1 do 0.

No ale w takim przypadku przesuwasz o 1, i dostaniesz dwa pierwsze piksele z ujemnym koordynatem - czyli tym razem zamiast ostatniego, dwa razy skopiujesz pierwszy piksel. Tymczasem ostatni nie będzie kopią ostatniego, tylko znajdzie się gdzieś pomiędzy przedostatnim a ostatnim - czyli w zasadzie będzie nawet gorzej niż było bez przesunięcia :D

Ma to z pewnością jakiś sens, ale nadal pierwszy i ostatni piksel będą po prostu skopiowane.

Tak, ale to nie jest problemem.

Zobrazuj to sobie tak: masz pewien odcinek AB, na którym leżą równomiernie rozłożone punkty (piksele). Ten odcinek to całość Twojego obrazka, który skalujesz. Długość odcinka jest w tej chwili bez znaczenia. Pierwszy i ostatni punkt (piksel) leżą odpowiednio na początku i końcu odcinka. Robiąc upscaling chcesz mieć ten sam obrazek, ale z większą liczbą pikseli (bo przeskalowany) - początek i koniec się nie zmienią, dokładasz jedynie więcej punktów na odcinku. Po upscalingu masz znowu odcinek a na nim punkty - jest ich więcej, są gęściej ułożone zatem masz więcej pikseli, te w środku mogą zmienić położenie ale skrajne nie mają ku temu powodów ;)

Nie czytalem dokladnie calosci rozwazan, wiec moze cos powtorze (ale chyba nie). Pierwszy przyklad zapisany nieco inaczej i bez blednych wnioskow:

dst    src_from  src_to
0   -> 0         0.71428 - interpolacja miedzy pikselem 0 a 0, czyli kopiowany piksel 0
1   -> 0.71428   1.42857 - interpolacja miedzy pikselem 0 a 1. wage piskela 0 mozna policzyc np. tak: w0 = (1 - 0.71428) / 0.71428. waga piksela 1: (1.42857 - 1) / 0.71428 == 1 - w0
2   -> 1.42857   2.14286 - interpolacja miedzy pikselem 1 a 2
3   -> 2.14286   2.85714 - kopiowany piksel 2
4   -> 2.85714   3.57143 - interpolacja miedzy pikselem 2 a 3
5   -> 3.57143   4.28571 - interpolacja miedzy pikselem 3 a 4
6   -> 4.28571   5       - kopiowany piksel 4

Liczac jak powyzej powiekszajac np. 10 razy czarno biala siatke zostana zachowane wyrazne przejscia miedzy jasnosciami, czyli inaczej niz w chyba wiekszosci programow gdzie dodawane sa rozne odcienie szarosci.

Pozostając w temacie skalowania, tym razem staram się sklecić coś do zmniejszania obrazu (downsamplingu). Wykombinowałem taką koncepcję, żeby obcinać wszystkie piksele w równomiernym stopniu, a potem po prostu usuwać powstałe w ten sposób "odstępy" między nimi. Na przykładzie:

7 zmniejszamy do 5, więc jak poprzednio R = 5/7 = 0,714

To oznacza, że każdy piksel musi zostać obcięty o 0,2857 (bo 1 - 0,7143 = 0,2857), a następnie przesunięty o tę właśnie wartość w lewo, czyli:

Piksel 0 nowego obrazu = (Piksel 0 pierwotnego obrazu * 0,714) + (Piksel 1 pierwotnego obrazu * 0,286)
Piksel 1 nowego obrazu = (Piksel 1 pierwotnego obrazu * 0,429) + (Piksel 2 pierwotnego obrazu * 0,571)
Piksel 2 nowego obrazu = (Piksel 2 pierwotnego obrazu * 0,143) + (Piksel 3 pierwotnego obrazu * 0,714) + (Piksel 4 pierwotnego obrazu * 0,143)
Piksel 3 nowego obrazu = (Piksel 4 pierwotnego obrazu * 0,571) + (Piksel 5 pierwotnego obrazu * 0,429)
Piksel 4 nowego obrazu = (Piksel 5 pierwotnego obrazu * 0,286) + (Piksel 6 pierwotnego obrazu * 0,714)

Jaki jest więc problem? Że nie za bardzo widzę tutaj sposób, żeby "lecieć" w pętli po pikselach nowego obrazu, tak jak to robię przy skalowaniu w górę. A to dlatego, że tutaj każdy piksel nowego obrazu może być złożony z X pikseli pierwotnego obrazu - 2,3, 10 itd. Musiałbym więc do każdego takiego piksela "dopiąć" listę pikseli obrazu pierwotnego, z których się składa, a potem stosować pętlę w pętli. Zamiast tego lepszym rozwiązaniem wydaje się być pętla po obrazie pierwotnym i sprawdzanie na jakie piksele w nowym obrazie składa się dany piksel w obrazie pierwotnym. To wygodne, bo każdy taki piksel może "brać udział" w 1 lub 2 pikselach nowego obrazu (nigdy więcej i nigdy mniej).

Ktoś ma pomysł, jak to zunifikować? Tak, żebym zarówno przy skalowaniu w górę i w dół mógł zachować ten sam schemat mapowania pikseli (zawsze dla obrazu pierwotnego, albo zawsze dla nowego).

Nie wiem o co dokładnie chodzi, ale podejrzewam próbę wynajdywania koła na nowo.

Podam dla uproszczenia przykład skalowania wiersza (czyli jednowymiarowego odcinka). Potem już sobie można to uogólnić do skalowania dwywymiarowej bitmapy.

Bierzez sobie wiersz lub kolumnę i robisz z tego funkcję y(x)=V gdzie x to numer kolejnego piksela a V to wartość koloru pojedynczego kanału lub para (rg,b) czy (r,g,b,a) jeśli liczysz z przezroczystością (a od alpha), Masz więc osie X i Y, gdzie współrzędne X to kolejne numery elementów w wierszu, zaś Y to te wartości jakie przyjmumuje kolor. Odległości między kolejnymi elementami wiersza przyjmujesz sobie za wartość 1. To znaczy x1-x2=1.

Teraz aby przeskalować sobie taki wiersz musisz po prostu podzielić sobie obszar pomiędzy x0 oraz xN na odpowiednią ilość przedziałów. Właśnie po to przyjmuje się odległość między kolejnymi x skalowanego obrazu by można było trafić między punktami. Np. jeśli trafisz 0,36 jednostek na prawo od punktu x3 to przykładowo liczysz sobie najprymitywniejszą metodą y_poprzeskalowaniu_w_punkcie_którymśtam=y(x3)0,36+y(x4)(1-0,36). Przy pomniejszaniu obrazu punktów tych będzie mniej niż masz w wierszu znanych pikseli(tych z oryginalnego obrazu) przy powiększaniu więcej.

Zamienia się więc problem wartości piksela w problem znajdywania wartości funkcji w danym punkcie w momencie gdy wartości funkcji znane są tylko dla co któregoś punktu, a pomiędzy nimi już musisz w jakiś zorganizowany sposób zgadywać.

Żeby to przerobić na skalowanie wierszy i kolum jednocześnie musisz sobie to przerobić na znajdywanie punktu na dwywymiarowej płaszczyźnie.

Satanistyczny Awatar napisał(a):

Teraz aby przeskalować sobie taki wiersz musisz po prostu podzielić sobie obszar pomiędzy x0 oraz xN na odpowiednią ilość przedziałów. Właśnie po to przyjmuje się odległość między kolejnymi x skalowanego obrazu by można było trafić między punktami. Np. jeśli trafisz 0,36 jednostek na prawo od punktu x3 to przykładowo liczysz sobie najprymitywniejszą metodą y_poprzeskalowaniu_w_punkcie_którymśtam=y(x3)0,36+y(x4)(1-0,36).

To jest zbyt duze uproszczenie. Pomniejszanie nie rozni sie bardzo duzo od powiekszania i da sie napisac kod ktory bedzie dzialal jednoczesnie w obydwu kierunkach, ale w przypadku pomniejszania sensownosc interpolacji miedzy 2 pikselami jest mocno dyskusyjna. Np. piksel wyjsciowy moze byc zmapowany na zakres pikseli wejsciowych od 3.2 do 17.9. Owszem, mozna to policzyc inaczej, uzyskac pojedyncza wartosc reprezentujaca zakres i interpolowac 2 piksele, ale wybranie 2 pikseli z kilkunastu raczej nie da lepszych wynikow niz np. wybranie pojedynczego (np. INTER_NEAREST z opencv). W praktyce calkiem przyzwoite rezultaty daje policzenie sredniej wazonej (trzeba uwzglednic ulamkowe czesci pikseli na brzegach) dla wszystkich pikseli zrodlowych ktore odpowiadaja pikselowi docelowemu (czyli odpowiednik INTER_AREA z opencv).

Jedziesz jednym algorytmem i możesz sobie skalować szerokość i wysokość indywidualnie i mieć gdzieś czy dany wymiar powiększa, zmniejsza czy nie. Wystarcza? Wystarcza. Chcesz się bawić w mnożenie przypadków szczególnych? Droga wolna.

Najlepszą z metod skalowania jest chyba FFT.

1. robimy FFT obrazu, otrzymujemy tablicę współczynników o wymiarach obrazu

2. skalowanie:
   a. przy zmniejszaniu obrazu nic nie robimy, po prostu obcinamy tablicę, czyli odrzucamy część wsp.
   b. przy powiększaniu: należy dołączyć więcej wsp. do tablicy - jak?
   To jest w zasadzie dowolne, najprościej wyzerować, ale można także coś tam wpisywać... eksperymentalnie;
   warunkiem jest tu chyba, że te współczynniki powinny maleć z indeksem - im dalej tym mniejszy..

3. robimy odwrotną FFT.

Crow napisał(a):

Witam.

Staram się sklecić w miarę wydajny ale też szybki algorytm do skalowania bitmap.

W przypadku powiększania (upscaling) mój wybór padł na interpolację dwuliniową (bilinear), bo po prostu daje niezłe efekty niewielkim kosztem. Nie aż tak dobre jak bicubic, ale przy tym nie jest aż tak wymagająca obliczeniowo. Wydaję mi się, że wszystko robię dobrze, ale jedna rzecz nie daje mi spokoju, więc wyjaśnię po krótce o co chodzi (w przykładzie posłużę się "obrazem" 1D, złożonym z poziomej linii - tak dla ułatwienia).

Załóżmy, że mam obraz o szerokości 5, a chciałbym go przeskalować do szerokości 7. Najpierw muszę sobie wyliczyć współrzędne nowych pikseli względem tych pierwotnych.

R = nowa wielkość / oryginalna wielkość = 5/7 = 0,7142
Współrzędna X piksela z obrazu końcowego na obrazie pierwotnym = Współrzędna X piksela obrazu końcowego * R

Czyli kolejno:

X(0) = 0 * R = 0 (kopia piksela 0 z obrazu pierwotnego)
X(1) = 1 * R = 0,7142 (sub-piksel interpolowany pomiędzy pikselem 0 i 1)
X(2) = 2 * R = 1,4284 (sub-piksel interpolowany pomiędzy pikselem 1 i 2)
X(3) = 3 * R = 2,1426 (sub-piksel interpolowany pomiędzy pikselem 2 i 3)
X(4) = 4 * R = 2,8568 (sub-piksel interpolowany pomiędzy pikselem 2 i 3)
X(5) = 5 * R = 3,571 (sub-piksel interpolowany pomiędzy pikselem 3 i 4)
X(6) = 6 * R = 4,2852 (sub-piksel interpolowany pomiędzy pikselem 4 i 5)

Z powyższego wychodzi, że pierwszy piksel końcowego obrazu zawsze jest po prostu kopią pierwszego piksela z obrazu pierwotnego (bo cokolwiek pomnożone przez zero, zawsze da zero), natomiast wszystkie inne piksele są sub-pikselami leżącymi gdzieś na granicy dwóch pikseli pierwotnego obrazu. Tak powinno być? To niby nic wielkiego ale jakoś mi ten pierwszy piksel nie pasuje.

Bo to jest marna metoda.

Należy wyliczać średnią z... fragmentów obrazu, znaczy: całkować to, hihi!

W przypadku zmniejszania o 2 jest to proste:
new_color[i,j] = średnia z 4: 2x2 pikseli = (c[2i, 2j] + c[2i+1, 2j] + c[2i, 2j+1] + c[2i+1, 2j+1]) / 4

I. w przypadku skali niecałkowitej, np. 1/2.5, robimy podobnie: te skrajne dodajemy z wagą 0.5, a potem dzielimy sumę przez 2.5^2 = 6.25.

II. przy powiększaniu można stosować te... interpolacje.

@Crow: pytanie czego oczekujesz od swojego algorytmu. Algorytm, który przedstawiłeś to jakaś odmiana nearest neighbour interpolation, czyli znajdujesz sobie, który uważasz za bazowy, potem wyznaczasz jego sąsiadów, potem sąsiadów sąsiadów itp. Algorytmy z tej grupy są wydajne, natomiast ich słabością jest właśnie sytuacja w której masz duży kontrast pomiędzy pikselami sąsiadującymi z sobą (np. jest szeroka na jeden piksel linia biała, potem niebieska, potem czerwona itp. itd.).

Tutaj masz listę rodzin algorytmów do upscalingu: https://en.wikipedia.org/wiki/Comparison_gallery_of_image_scaling_algorithms
A tutaj masz zbiór ich implementacji wykorzystywanych w emulacji: https://en.wikipedia.org/wiki/Pixel-art_scaling_algorithms

Crow napisał(a):

Z powyższego wychodzi, że pierwszy piksel końcowego obrazu zawsze jest po prostu kopią pierwszego piksela z obrazu pierwotnego (bo cokolwiek pomnożone przez zero, zawsze da zero), natomiast wszystkie inne piksele są sub-pikselami leżącymi gdzieś na granicy dwóch pikseli pierwotnego obrazu. Tak powinno być?

Tak powinno być, dlatego że szerokość piksela wejściowego jest mniejsza od wyjściowego. Najlepiej pokaże to obrazek:

Jak widać, kolor pierwszego piksela pozostaje bez zmian, drugiego jest mieszanką pierwszego i drugiego, trzeciego jest mieszanką trzeciego i czwartego. Czwarty pozostaje bez zmian, kolejne są mieszankami, a ostatni też pozostaje bez zmian. Kolory pikseli brzegowych ulegną zmianie tylko w przypadku skalowania w dół oraz gdy sąsiadujące z nimi piksele mają inne kolory.

@Crow: do własnych zastosowań wykorzystuję algorytm Pana Davida E. Dirkse — A Bitmap Resize Algorithm, ostatnio na potrzeby Richtrisa, do skalowania zawartości stosu. Pełen opis algorytmu z rysunkami oraz kod źródłowy testowego projektu dla Delphi znajdziesz na jego stronie (u góry są przyciski do pobrania źródeł oraz binarki). Kod co prawda brzydki (wymaga sformatowania), ale za to jest wystarczająco efektywny i daje bardzo ładne rezultaty.

Demówka dołączona do źródeł mierzy czas skalowania i podaje wynik w mikrosekundach.

@furious programming:

A ten algorytm nie ma przypadkiem problemu, o którym wspominał @superdurszlak?

Załóżmy, że chcę przeskalować w dół z 7 do 5. Zgodnie z tym algorytmem powinienem to zrobić w ten sposób:

float F = 7/5 = 1.4

A potem:

0 * F = 0
1 * F = 1.4
2 * F = 2.8
3 * F = 4.2
4 * F = 5.6

Czyli mamy nierówność, zerowy piksel zostaje skopiowany, ale już ostatni stanowi mieszankę 5 i 6 piksela źródłowego. Drugi minus dostrzegam taki, że do skalowania pikseli i tak jest potrzebne 1/F czyli trzeba wykonać dodatkowe dzielenie.

Ja to rozwiązałem podobnie, ale (chyba) lepiej, bo z mniejszą ilość mnożenia i dzielenia. Tutaj przykład funkcji do skalowania w górę w pionie:

void Image::ScaleVerticalUp(int iHeight)
{
	int const NewSize = Data.Width * iHeight;
	Pixel* Output = new Pixel[NewSize]; 
	//Pixel to struktura stanowiąca maskę bajtową dla integera, z którego zbudowany jest bufor obrazka źródłowego { unsigned char B, G, R, A }
		
	memset(Output, 0, NewSize * sizeof(Output));

	//Data.Bits to bufor zawierający piksele obrazka źródłowego w formie jednowymiarowej tablicy integerów
	//Data.Width i Data.Height to wymiary obrazka źródłowego, a Data.Size to ilość jego wszystkich pikseli (Width * Height)

	float const Ratio = (static_cast<float>(Data.Height - 1) / static_cast<float>(iHeight - 1)) * 0.9999f, Dec = 1.0f - Ratio; 
	//tutaj zastosowałem metodę zaproponowaną przez durszlaka, oraz tą z algorytmu podlinkowanego przez ciebie :).
		
	float Value = 0.0f, Slice = 1.0f;
	Pixel* In_T = reinterpret_cast<Pixel*>(Data.Bits), * In_B = In_T + Data.Width, * Out = Output, * RowEnd = &Output[Data.Width];
	Pixel* const ColumnEnd = &Output[NewSize]; 
               
	for (; Out < ColumnEnd; RowEnd += Data.Width)
	{
		for (; Out < RowEnd; Out++, In_T++, In_B++)
		{
			Out->R = (In_T->R * Slice) + (In_B->R * Value);
			Out->G = (In_T->G * Slice) + (In_B->G * Value);
			Out->B = (In_T->B * Slice) + (In_B->B * Value);
		}

		if (static_cast<int>(Value + Ratio)) Value -= Dec;
		else
		{
			Value += Ratio;
			In_T -= Data.Width;
			In_B -= Data.Width;
		}

		Slice = 1 - Value;
	}

	delete[] Data.Bits;
	Data.Bits = reinterpret_cast<int*>(Output);
	Data.Height = iHeight;
	Data.Size = NewSize;
}

Problem miałem już w zasadzie tylko z zaokrąglaniem floatów, bo w testach mi wyszło, że dla niektórych wartości (długości i szerokości obrazka) 10 razy działało dobrze, a potem raz wywalało błąd, bo za każdym razem floaty były zaokrąglane trochę inaczej i czasem wyłaziło mi za bufor... No ale zastosowałem ten trick z przemnożeniem przez 0.9999 i pomogło. Czyli jednak się przydało, dzięki ;).

Wydaje mi się, że jeśli skalujesz w dół to wynikowy piksel może być średnią z więcej niż dwóch wejściowych pikseli. Dla przykładu jeśli skalujesz 10x w dół (w jednym wymiarze) to wynikowy piksel jest średnią z 10 pikseli na wejściu.

O ile dobrze rozumiem to jeśli odwrócimy proces opisany przez @furious programming

i będziemy skalować z 7 pikseli do 5 to okaże się, że środkowy wynikowy piksel będzie średnią ważoną z 3 wejściowych pikseli.

Crow napisał(a):

@furious programming:

A ten algorytm nie ma przypadkiem problemu, o którym wspominał @superdurszlak?

Załóżmy, że chcę przeskalować w dół z 7 do 5. Zgodnie z tym algorytmem powinienem to zrobić w ten sposób:

float F = 7/5 = 1.4

A potem:

0 * F = 0
1 * F = 1.4
2 * F = 2.8
3 * F = 4.2
4 * F = 5.6

Wyznaczyłeś więc krawędzie pikseli tak jak tutaj jest to opisane: http://entropymine.com/imageworsener/matching/
Wynikowe piksele to średnia ważona z tego co jest pomiędzy pikselami, a więc:

• pix_out_0 = (pix_in_0 * 1 + pix_in_1 * 0.4) / 1.4
• pix_out_1 = (pix_in_1 * 0.6 + pix_in_2 * 0.8) / 1.4
• pix_out_2 = (pix_in_2 * 0.2 + pix_in_3 * 1 + pix_in_4 * 0.2) / 1.4 <- uwaga: tutaj uśredniamy 3 piksele, mimo iż skalowanie to tylko 1.4x w dół!
• pix_out_3 = (pix_in_4 * 0.8 + pix_in_5 * 0.6) / 1.4
• pix_out_4 = (pix_in_5 * 0.4 + pix_in_6 * 1) / 1.4

Proces jest więc symetryczny, a każdy piksel ma taki sam wpływ na wynik. Suma nieznormalizowanych wag (trzeba podzielić przez 1.4) dla każdego piksela wejściowego jest równa:

• pix_in_0 = 1
• pix_in_1 = 0.4 + 0.6 = 1
• pix_in_2 = 0.8 + 0.2 = 1
• pix_in_3 = 1
• pix_in_4 = 0.2 + 0.8 = 1
• pix_in_5 = 0.6 + 0.4 =1
• pix_in_6 = 1

Crow napisał(a):

A ten algorytm nie ma przypadkiem problemu, o którym wspominał @superdurszlak?

Masz na myśli poniższe słowa?

superdurszlak napisał(a):

Ale to nie naprawi "asymetrii" całego przedsięwzięcia, bo interpolowane piksele nadal będą miały tendencję by ciążyć w górną lewą stronę :P

Raczej nie ma takiej tendencji. Piszę „raczej”, bo nie znam każdego szczegółu tego algorytmu, a nawet jeśli takie niuanse w nim istnieją, to nie są w żaden sposób zauważalne w projekcie, w którym go wykorzystuję. Po prostu jest mi to obojętne, bo jakość wynikowych bitmap zadowala mnie w pełni (nawet jeśli sobie kuknę pod lupą na kolory pikseli), a efektywność algorytmu jest wystarczająco wysoka.

Jeśli chcesz wiedzieć na 100% czy interpolacja będzie wyciągana do lewego górnego rogu, to sprawdź działanie tego algorytmu na takich testowych bitmapach, które po przeskalowaniu uwidocznią tego typu mankamenty. Program testowy jest dostępny do pobrania, więc wystarczy jedynie trochę poklikać.

W razie czego możesz ten algorytm zmodyfikować według wskazówek @superdurszlak i przesuwać koordynaty o 0.5, zanim użyjesz ich jako indeksów. Pamiętaj tylko, aby zabezpieczyć się przed wyjątkiem związanym z „off by one”.

Wibowit napisał(a):

O ile dobrze rozumiem to jeśli odwrócimy proces opisany przez @furious programming

i będziemy skalować z 7 pikseli do 5 to okaże się, że środkowy wynikowy piksel będzie średnią ważoną z 3 wejściowych pikseli.

Dokładnie tak będzie. A to przy okazji pokazuje, że tego typu skalowanie jest stratne, bo ponowne zeskalowanie do rozmiaru źródłowego da nieco inny obraz niż ten źródłowy (kolory pikseli będą inne niż na początku) i jest to (d)efekt spodziewany.

A co powiecie na taką implementację skalowania w poziomie w dół? Chodzi mi głównie o to, czy nie przedobrzyłem ze wskaźnikami. Moim priorytetem jest szybkość :).

void Image::ScaleHorizontalDown(int iWidth)
{
	struct Pixel
	{
		unsigned char B, G, R, A;
	};
	struct FloatPixel
	{
		float B = 0.0f, G = 0.0f, R = 0.0f, A;
	};

	int const NewSize = iWidth * Data.Height;
	Pixel* Output = new Pixel[NewSize];
	FloatPixel* Safe = new FloatPixel[Data.Height];

	float const Ratio = (static_cast<float>(iWidth) / static_cast<float>(Data.Width)) * 0.9999f, Dec = 1.0f - Ratio;
	float Value = 0.0f, Slice;

	Pixel* In = reinterpret_cast<Pixel*>(Data.Bits), * Out = Output, * ColumnEnd = reinterpret_cast<Pixel*>(&Data.Bits[Data.Size]); 
	Pixel* const RowEnd = reinterpret_cast<Pixel*>(&Data.Bits[Data.Width]);

	for (; In < RowEnd; In -= Data.Size - 1, ColumnEnd++, Safe -= Data.Height)
	{
		if (static_cast<int>(Value + Ratio))
		{
			Slice = 1 - Value;
			Value -= Dec;
			for (; In < ColumnEnd; In += Data.Width, Out += iWidth, Safe++)
			{
				Out->R = Safe->R + (In->R * Slice);
				Out->G = Safe->G + (In->G * Slice);
				Out->B = Safe->B + (In->B * Slice);

				Safe->R = (In->R * Value);
				Safe->G = (In->G * Value);
				Safe->B = (In->B * Value);
			}
			Out -= NewSize - 1;
			Safe -= Data.Height;
		}
		else
		{
			Value += Ratio;
			for (; In < ColumnEnd; In += Data.Width, Safe++)
			{
				Safe->R += (In->R * Ratio);
				Safe->G += (In->G * Ratio);
				Safe->B += (In->B * Ratio);
			}	
		}
	}

	delete[] Safe;
	delete[] Data.Bits;
	Data.Bits = reinterpret_cast<int*>(Output);
	Data.Width = iWidth;
	Data.Size = NewSize;
}