Wstęp

Wielu młodych ludzi nie zdaje sobie sprawy, że matematyka otacza nas codziennie.
Dla większości wzory wyuczone w szkole to po prostu puste regułki.
- "Do czego mogą przydać się funkcje czy ich przekształcenia na układzie współrzędnych?" – pytają, wzruszając ramionami.
W mojej pracy postaram się udowodnić, że wszystkie te gałęzie matematyki mają praktyczne zastosowanie, że dotyczą one Twojego życia częściej niż Ci się wydaje. Pokażę Ci, że matematyka może mieć zastosowanie praktyczne, tam gdzie się tego nie spodziewasz, a ponadto wyjaśnię Ci jak to działa.

W mojej pracy opowiem Ci o technice obróbki cyfrowego obrazu – interpolacji biliniowej. Tak naprawdę masz z nią do czynienia na co dzień – przeglądając zdjęcia, portale internetowe czy nawet grając w gry... Ale cóż to takiego ta interpolacja biliniowa?
Zanim to wyjaśnię przybliżę Ci koncepcję samej interpolacji.

Koncepcja

Interpolacja w matematyce pomaga w oszacowaniu nowej wartości pomiędzy wartościami, które już znamy.
Zobaczmy to na przykładzie. Chcemy dowiedzieć się jaka była temperatura na dworze, w południe, jeśli wiemy, że o 8⁰⁰ było 20^oC, a wieczorem o 18⁰⁰ było 28^oC

Dzięki interpolacji jesteśmy w stanie oszacować nieznaną nam wartość (zielony punkt)  na podstawie danych,
które już znamy (czerwone punkty).

Bitmapa

Każdy obraz wyświetlany na ekranie Twojego monitora składa się z małych punkcików zwanych pikselami.
Każdy piksel ma określony kolor, na który składają się trzy podstawowe kolory – czerwony, zielony i niebieski (RGB).
Można to zobrazować podobnie jak temperaturę za pomocą układu współrzędnych:

Czyli obraz to tak naprawdę zbiór bardzo małych punktów (pikseli) o ściśle określonym kolorze. Kiedy znacznie powiększymy jakieś zdjęcie to możemy zaobserwować te piksele:

Jak widzisz, przy powiększaniu obrazka, bez użycia interpolacji biliniowej dają się dostrzec coraz wyraźniejsze piksele.
Hmmm… Zobaczmy w jaki sposób komputery powiększają obraz.

Brak algorytmów interpolacji

Aby zrozumieć jak komputery powiększają obraz musimy zacząć od rzeczy najprostszych. Zrezygnujmy z dużych obrazków i algorytmów. Zobacz co się stanie kiedy komputer powiększy bardzo mały, bo 4-pikselowy obraz 2,5-raza bez użycia żadnego algorytmu interpolacji:

Znowu znane piksele zostały przesunięte na odpowiednie miejsca, ale między nimi powstały dziury. Dziury te zostały zaznaczone kolorem czarnym, ale jest to tylko kolor umowny, gdyż tak na prawdę nie wiadomo jaki powinny mieć kolor. Wniosek jest prosty - należy ustalić, używając odpowiedniego algorytmu, jakie kolory powinny mieć czarne/nieznane piksele między znanymi pikselami. Użyjmy do tego celu najprostszego rodzaju interpolacji - najbliższego sąsiada (ang. Nearest neighbour).

Interpolacja metodą najbliższego sąsiada

Tak jak to bywa w algorytmach trzeba ustalić pewien przepis, który ustalałby zasady dobierania kolorów do sąsiednich pikseli:

Dzięki temu prostemu i szybkiemu algorytmowi otrzymujemy taki obraz:

Interpolacja biliniowa

Polega to na tej samej zasadzie co oszacowywanie temperatury kilka stron wcześniej, z tą różnicą, że teraz nie będziemy szukać wartości temperatury, ale koloru. To całkiem proste.
Najpierw należy przeprowadzić interpolację liniową wzdłuż osi OX, czyli wyznaczyć R₂ między punktami Q₁₂ do Q₂₂ oraz R₁ między punktami Q₁₁ do Q₂₁.
Po czym jeszcze raz przeprowadzić interpolację liniową, tym razem wzdłuż osi OY, czyli między punktami R₁ i R₂ otrzymując w ten sposób punkt P, który posiada teraz wartość idealnie komponującą się z punktami Q₁₂, Q₂₂, Q₁₁ i Q₂₁

Poniżej widzimy 4 niebieskie słupki, o różnych wysokościach (wartościach). Wysokość zielonego słupka została oszacowana za pomocą interpolacji biliniowej. Bez względu na jego położenie między czterema, niebieskimi słupkami, zawsze będzie on mógł osiągnąć taką wysokość, aby być w doskonałej relacji z innymi słupkami.

Tak jak wspomniałem na początku, każdy piksel ma ściśle określony kolor na, który składają się 3 podstawowe barwy – czerwony zielony i niebieski (RGB). To w jakiej proporcji je zmieszamy, ma wpływ na kolor wypadkowy piksela.

Potraktujmy słupki jak piksele, a ich wysokości jak nasycenie kolorom. Każda wysokość słupka to inny kolor. Znajdźmy brakujące piksele za pomocą interpolacji biliniowej.

Piksel Q₁₂ składa się z mieszanki kolorów RGB (ang. Red Green Blue), które nanosimy na układ współrzędnych jako 3 punkty: Q_12.R, Q_12.G, Q_12.B
Analogicznie postępujemy z pikselem Q₂₂
Teraz należy wyznaczyć wzór funkcji liniowej dla każdego koloru. Utwórzmy go najpierw dla koloru czerwonego:

Graphics::TBitmap* __fastcall ResizeBilinear(Graphics::TBitmap *bmpin, int DestWidth, int DestHeight)
{
  Graphics::TBitmap *bmpout=new Graphics::TBitmap();
  bmpout->Width=DestWidth; //nowa szerokosc
  bmpout->Height=DestHeight; //nowa wysokosc
  
  double p,q;
  int x,y,k,j;
  double px,py;
  double dx,dy;
  double kolor;
  int sx,sx2,sy;
  Byte c1,c2;
  double c_1,c_2;
  Byte *l1in,*l2in,*lout;
  int neww=DestWidth,
      newh=DestHeight,
      oldw=bmpin->Width,
      oldh=bmpin->Height;

  bmpin->PixelFormat=pf24bit;
  bmpout->PixelFormat=pf24bit;

  p=(double)neww/(double)oldw;
  q=(double)newh/(double)oldh;

  for(y=0;y<newh;y++)
  {
      py=(double)y/q;
      lout=(Byte*)bmpout->ScanLine[y];
      if(py>=oldh-1)
      {
        sy=oldh-2;
        dy=1;
      }
      else
      {
        sy=(int)(floor(py));
        dy=py-sy;
      }
      l1in=(Byte*)bmpin->ScanLine[(int)sy];
      l2in=(Byte*)bmpin->ScanLine[(int)sy+1];
      j=0;
      for(x=0;x<neww;x++)
      {
        px=(double)x/p;
        if(px>=oldw-1)
        {
          sx=oldw-2;
          dx=1;
        }
        else
        {
          sx=(int)(floor(px));
          dx=px-sx;
        }
        sx2=sx+1;
        sx+=sx<<1;
        sx2+=sx2<<1;
        for(k=0;k<3;k++)
        {
          c1=l1in[sx+k];
          c2=l1in[sx2+k];
          c_1=c1+dx*(c2-c1);
          c1=l2in[sx+k];
          c2=l2in[sx2+k];
          c_2=c1+dx*(c2-c1);
          kolor=c_1+dy*(c_2-c_1);
          lout[j]=(Byte)(floor(kolor));
          j++;
        }
      }
  }
  return bmpout;
}
      

procedure ResizeBilinear(Src: TBitmap; var Dest: TBitmap; DestWidth, DestHeight, SrcWidth, SrcHeight: integer);
var
	hScale, wScale: double;
	f1, f2, f3, f4, f12, f34, fNew: TRGBTriple;
	temp1, temp2, tempDst: PRGBTripleArray;
	x, y: double;
	x1, x2, y1, y2, i, j: integer;
begin
	Dest := TBitmap.Create;
	Dest.PixelFormat := pf24Bit;
	Dest.Width := DestWidth;
	Dest.Height := DestHeight;
	Src.PixelFormat := pf24Bit;
	Src.Width := SrcWidth;
	Src.Height := SrcHeight;
	hScale := DestHeight / SrcHeight;
	wScale := DestWidth / SrcWidth;
	for i := 0 to DestHeight - 1 do
	begin
		 x := i / hScale;
		 x1 := trunc(x);
		 x2 := x1 + 1;
		 if x2 > SrcHeight - 1 then x2 := SrcHeight - 1;
		 temp1 := Src.ScanLine[x1];
		 temp2 := Src.ScanLine[x2];
		 tempDst := Dest.ScanLine[i];
		 for j := 0 to DestWidth - 1 do
		 begin
			 y := j / wScale;
			 y1 := trunc(y);
			 y2 := y1 + 1;
			 if y2 > SrcWidth - 1 then y2 := SrcWidth - 1;
			 f1 := temp1^[y1];
			 f2 := temp1^[y2];
			 f3 := temp2^[y1];
			 f4 := temp2^[y2];
			 f12.rgbtRed := trunc(f1.rgbtRed + (y - y1) * (f2.rgbtRed - f1.rgbtRed));
			 f12.rgbtGreen := trunc(f1.rgbtGreen + (y - y1) * (f2.rgbtGreen - f1.rgbtGreen));
			 f12.rgbtBlue := trunc(f1.rgbtBlue + (y - y1) * (f2.rgbtBlue - f1.rgbtBlue));
			 f34.rgbtRed := trunc(f3.rgbtRed + (y - y1) * (f4.rgbtRed - f3.rgbtRed));
			 f34.rgbtGreen := trunc(f3.rgbtGreen + (y - y1) * (f4.rgbtGreen - f3.rgbtGreen));
			 f34.rgbtBlue := trunc(f3.rgbtBlue + (y - y1) * (f4.rgbtBlue - f3.rgbtBlue));
			 fNew.rgbtRed := trunc(f12.rgbtRed + (x - x1) * (f34.rgbtRed - f12.rgbtRed));
			 fNew.rgbtGreen := trunc(f12.rgbtGreen + (x - x1) * (f34.rgbtGreen - f12.rgbtGreen));
			 fNew.rgbtBlue := trunc(f12.rgbtBlue + (x - x1) * (f34.rgbtBlue - f12.rgbtBlue));
			 tempDst^[j] := fNew;
		 end;
	end;
end;
      

procedure ResizeNearestNeighbor(Src: TBitmap; var Dest: TBitmap; DestWidth, DestHeight, SrcWidth, SrcHeight: integer);
var
	hScale, wScale: double;
	fNew: TRGBTriple;
	tempSrc, tempDst: PRGBTripleArray;
	x, y, i, j: integer;
begin
	Dest := TBitmap.Create;
	Dest.PixelFormat := pf24Bit;
	Dest.Width := DestWidth;
	Dest.Height := DestHeight;
	Src.PixelFormat := pf24Bit;
	Src.Width := SrcWidth;
	Src.Height := SrcHeight;
	hScale := DestHeight / SrcHeight;
	wScale := DestWidth / SrcWidth;
	for i := 0 to DestHeight - 1 do
	begin
		x := round(i / hScale);
		if x > SrcHeight - 1 then x := SrcHeight - 1;
		tempSrc := Src.ScanLine[x];
		tempDst := Dest.ScanLine[i];
		for j := 0 to DestWidth - 1 do
		begin
			y := round(j / wScale);
			if y > SrcWidth - 1 then y := SrcWidth - 1;
			fNew := tempSrc^[y];
			tempDst^[j] := fNew;
		end;
	end;
end;
      

Zakończenie

Teraz już wiesz, że bez matematyki nie można przeglądać zdjęć, czy nawet włączyć komputera… Cała dzisiejsza informatyka,  stoi na fundamencie liczb. To ona rządzi światem. Pamiętaj o tym kiedy następnym razem włączysz komputer ;)

Dziękuję za uwagę.

Damian Drygiel

I Liceum Ogólnokształcące im. Stefana Czarnieckiego w Chełmie.

Bibliografia: