Algoritmus na 4-bodovou kalibraci 2D mapy?

Zdar,
neresil tu nekdo nahodou problem kalibrace 2D mapy?
Potreboval bych napsat fci, ktere dam 4 2D souradnice bodu na mape (v pixelech) a 4 2D souradnice (v nejakem systemu, treba wgs), a nasledne mi tato fce podle zadaneho bodu [x,y] vrati prepoctene souradnice [x',y']v pixelech (a naopak, inverzni fce).
Mam napsanou jednochou verzi pro 2-bodovou kalibraci, ktera ale predpoklada ze osy obou sour. systemu sou rovnobezne, zistil sem vsak ze mapa je asi o 0.5stupne pootocena...

BTW mozna by stacily jen 3 body, ale asi by musely tvorit pravouhly trojuhelnik..

EDIT:
Aby to bylo jasny, tak tady este nacrtek (znam x1-4,y1-4 a jejich obrazy, hledam funkci f)
http://rayer.ic.cz/350d/calmap/2dtran.gif
Idealni by byl zdrojak v C :) ale postaci nejaky odkaz kde se tohle resi, zatim sem nic rozumnyho nenasel.

Tak uz zhruba vim jak na to, jen este nakej alg. na spocteni inverzni matice 9xn

Pokud si dobře vzpomínám na algebru, tak inverzní matice existuje jen ke čtvercové , protože matici a inverzní matice musejí být navzájem vynásobitelné, což je u čtvercových zaručeno.
Jeden postup je:
napsat si vedle matice jednotkovou
původní matici Gaussovou eliminační metodou upravit na jednotkovou a stejné operace provádět s tou druhou. Výsledkem je, že z původně jednotkové matice se stane inverzní.
Tady jsem vygooglil popis
http://www.kolej.mff.cuni.cz/~lmotm2...ml/node55.html
Je tady uvedený i druhý způsob přes determinanty, ale počítat determinanty matice rozměru +-9 je IMHO blbost, složité a dlouhé. Šel bych první cestou.

Kdyby byl zájem můžu se mrknout, jestli ještě najdu skripta, pak bych je naskenoval.

Kód:

---


for (radek = 0; radek < n; radek ++) { /* projit vsechny radky */
  pivot = matice[radek][radek];
  for (i = 0; i < n; i++)
      matice[radek][i] /= -1 * pivot;    /*vyrobit jednicku na miste na hlavni diagonale */
 
  for (i = radek; i < n - 1; i++) {      /* projdu vsechny nizsi radky mimo posledniho */
      pivot = matice[i + 1][i] / matice[i][i] * -1;  /* cislo, kterym musim vynasobit radek a pricist k nizsimu radku */
      for (j = 0; j < n; j++) {  /* tady nasobim ten radek a pricitam ke spodnimu */
        matice[i + 1][j] += matice[i][j] * pivot
      }
  }
}

/* opakovat cele obracene, to jest odspoda nahoru a vytvaret nuly nad hlavni diagonalou. Ty same operace provadet s tou druhou matici */

---

Je to jenom takovy lehoučký nástřel pro inspiraci, kdoví jestli by někde nějaký index nepřetekl apod. Možná je tam i logická chyba. Kdo ví :). Ale zhruba takhle se to dělá.

Jenom bych podotkl, ze vypocet pres determinanty neni obecne slozitejsi. Mnohdy (u "nehezkych" cisel nebo u matic s neznamyma) je to vyhodnejsi nez pres jednotkovou matici. Navic u algoritmizace jsou potom determinanty/subdeterminanty zasadni.

Citace:

---

Původně odeslal Haste

Jenom bych podotkl, ze vypocet pres determinanty neni obecne slozitejsi.

---

To je velká pravda.
Ale dodal bych, že než se člověk dostane na matici 3x3, tak v případě matice 9x9 to bude patrně několik rekurzivních volání. Pokud si dobře vzpomínám, tak spočítat determinant matice n x n, kde n > 3 znamená spočítat 1 determinant matice n x n a n-1 determinantů matice rozměru n - 1. A pro každou to takhle rozvíjet až do řádu 3x3. Takže to narůstá neskutečným tempem a trvalo by to neskutečně dlouho. Učitel matematiky nám jednou demonstroval, že počítat takhle determinant matice 100x100 by i nejvýkonějšímu superpočítači trvalo miliardy let (možná desítky miliard).
Pro matici 9x9 to myslím znamená následující:
-1x determinant matice 9x9
-8 x determinant matice 8x8
(snad jsem to řekl dobře, nechce se mi hledat skripta z algebry).
Leda by se ty determinanty počítaly jinak (úprava na dolní trojúhelníkovou a pak vynásobit prvky na hlavní diagonále ?????), ale to je pak rovnou možné počítat tu inverzní matici tou první metodou.

Diky,
uz sem sehnal nakej C kod na inv. matice, sou tam hned 2 algoritmy: Gauss routine a Crout routine. Gauss ma bejt rychlejsi a mene presnej, v praxi matice 1000x1000 trvala 0,4s a rozdil chyby byl par chlupu na poslednim desetinnym miste.

K ty matici m*n, pry existuje neco jako pseudoinverzni matice, ktera je prave pro obdelnikovy a pocita se: (AT*A)^-1*AT (kde AT je transponovana k A)

mi neni jasne to zadani. to jsou ctyri body nebo co ?

Citace:

---

Původně odeslal Kon

mi neni jasne to zadani. to jsou ctyri body nebo co ?

---

Obrazek uz sem odmazal, neb ti co k tomu meli co rict uz rekli, naky algoritmy mam na papire, ale momentalne neni cas si s tim hrat.
Jak bylo zmineno vyse, slo o to najit matici zobrazeni pomoci ctyr (+-) kalibracnich bodu u nich znam vzor i obraz, tak abych mohl prepocitat souradnice libovolneho bodu na nove transformovane souradnice. Zobrazeni ma zohlednit rotaci a zmenu meritka na osach, v obou soustavach sou souradnice ortogonalni.

pokud jsou soustavy ortogonální, pak nechápu proč máš 4 body

Citace:

---

Původně odeslal Kon

pokud jsou soustavy ortogonální, pak nechápu proč máš 4 body

---

No vsak sem psal, ze by mozna stacily 3. Ten algoritmus co sem sehnal tak bere obecne 4 a vice bodu, takze zvladne korikovat i dalsi deformace, coz se muze v budoucnu hodit...

no pokud mas univerzalni algoritmus pak jo, muze to byt zese na ukor rychlosti.
Jinak v ortogonalnim systemu vzhledem k jinemu muze dojit k posunu, otoceni, zmene meritka takze tech bodu moc nepotrebujes ... staci ti pracovat s maticemi 2x2

No tak muzes nahodit tu zjednodusenou variantu, ale asi to uz udelam rovnou poradne, o rychlost az tak nejde prepocitava se jen pri pohybu mysi nad mapou.

Citace:

---

Původně odeslal RayeR

No tak muzes nahodit tu zjednodusenou variantu, ale asi to uz udelam rovnou poradne, o rychlost az tak nejde prepocitava se jen pri pohybu mysi nad mapou.

---

Kdyz si vemem v potaz rychlost poolingu nekterych mysek, tak to muze byt i problem. Hodne Razeru/Logitechu mivaji pooling 250-1000Hz a to uz se projevi. Bys tam mel dat spis fixed timing, aby nedochazelo ke zpomaleni. Ale to jen tak na okraj...

No jedna vec je jak windows rychle cte pozici z mysiportu a druha vec jak rychle se stiha vykreslovat kurzor nebo cokoliv na obrazovce, coz bude tak o rad min (vsync) jak ten 1kHz, ale i tak myslim ze to jeden vektor s matici stihne nasobit mnoohem rychleji.

Citace:

---

Původně odeslal RayeR

No jedna vec je jak windows rychle cte pozici z mysiportu a druha vec jak rychle se stiha vykreslovat kurzor nebo cokoliv na obrazovce, coz bude tak o rad min (vsync) jak ten 1kHz, ale i tak myslim ze to jeden vektor s matici stihne nasobit mnoohem rychleji.

---

U WinAPI nejde o vsync. Zpravy ti do smycky chodi na MouseMove a to je opravdu az 1000x za sekundu podle poolingu. Vykreslovani kurzoru ve 2D je taky mnohem rychlejsi nez jak si myslis, pokud tedy jde o HW kurzor, ktery dnes vyuzivaji vsechny GK, ale opravdu tady nejde jeho vykresleni, ale o pocet zprav ve smycce. Podle me bys mel lepsi, kdybys to dal na wm_paint ci neco podobneho a nechal tam navic jasny interval. Treba 1/60 sekundy.

No to je stejne fuk, protoze nepisu pro winy :) asi sem nemel to slovo vyslovovat :)

Citace:

---

Původně odeslal RayeR

No to je stejne fuk, protoze nepisu pro winy :) asi sem nemel to slovo vyslovovat :)

---

To si nemel ;) Jenom me to tak napadlo, ze by to zpomalovalo. Neco podobneho sem kdysi resil v nasem editoru.