Сателитни снимки, плакати и Google maps

Предаването Space night по Баварската телевизия за пръв път ми отвори очите за красотата на сателитните снимки. Няколко пъти седмично, късно през нощта и на фона на релаксиращи chill out и easy listening парчета пускаха снимки на Земята, правени от космоса от астронавти и сателити. След време открих изумителната Google Earth, с която и до днес понякога прекарвам часове наред. Започнах да купувам плакати от серията Space shots и да си крася къщата с тях. Плакатите са си много хубави, но имат няколко недостатъка. Първо, много са скъпи. Второ, част от тях са в много идиотски размери (вероятно американски), за които е много трудно, ако не и невъзможно да се намерят рамки. И трето, най-важно, от Space shots нямат всичко, което ми се иска и както ми се иска. Така че миналата седмица се залових сама да сглобя изображения на местата, които ме интересуват.

Това обаче се оказа нелека задача. Първият ми импулсивен подход беше да експортирам изображения едно по едно от Google Earth и после да ги сглобя с програма за панорамни снимки като PTGui. Реших като за начало да съставя едно много детайлно изображение на цяла София. За целта увеличих колкото беше възможно без да се получи размазване и започнах да обхождам картата квадрант по квадрант, експортирайки изображенията. Проблемът беше, че на експортираното изображение се виждаха някои от надписите, както и навигацинното колело на Google Earth в горния десен ъгъл. Така че на практика можех да използвам само част от изображението. И понеже правех всичко на ръка, не можех да създам еднакви по големина, идеално допиращи се отрязъци, които след това просто да залепя един за друг. Налагаше се отрязъците да се застъпват. За да сглобя по подобен начин цяла София ми бяха необходими приблизително 14 стъпки по хоризонталата и 30 стъпки по вертикалата, което прави над 400 отделни отрязъка. Понеже съм си търпелива за подобни неща, направих го. Отне ми... известно време. Неприятната изненада дойде след това, когато установих, че PTGui не може да се справи със задачата - не можеше да открие допирателните точки и искаше да ги задавам една по една за всяка двойка допиращи се отрязъци. Пробвах да направя два реда на ръка във Photoshop но установих, че и това е непосилна задача - ако изображенията не се свързват едно с друго с точност до пиксел, грешките се акумулират и се получават видими размествания.

Следващата стъпка беше да потърся някаква програма за целта - в крайна сметка едва ли съм единствената с подобни мераци. За съжаление обаче не намерих нищо смислено - програмите, които автоматизираха процеса, оставяха надписите по изображенията или не можеха да напаснат изрязаните от мен парчета. Попаднах обаче на един php-скрипт, който използва Google maps. Оказа се, че това е много по-лесен вариант, тъй като картите на Google maps се пазят и прехвърлят под формата на парченца (tiles) с размер 256х256 пиксела, във формат jpeg. Всяко парченце си има собствен "адрес" в рамките на цялата карта. Ако човек знае адресите на необходимите парчета, може просто да си ги свали от Google и да си ги сглоби като мозайка.

Първата стъпка е да се разбере геометричното кодиране на отделните парченца. Оказва се, че Google използват така нареченото quadtree, за да структурират картите си. Това е елегантен метод от компютърната графика, при който всяко изображение "съдържа" в себе си четири подизображения, представящи го в по-голям детайл, които от своя страна съдържат по четири подизображения и т.н. С други думи, от всяко изображение имаме възможност да увеличим (zoom-нем) в четири посоки - на северозапад, североизток, югоизток и югозапад и така до определена дълбочина. При Google четирите посоки на zoom-ване се кодират с q (северозапад), r (североизток), s (югоизток) и t (югозапад):



Адресът на всяко отделно квадратче се образува, като се изброят едно след друго всички увеличения (zoom-вания), необходими за да се стигне до него. Първото изображение има адрес t (по конвенция, със същия успех можеше да е q, r или s). Това е квадратчето, представящо цялата карта на земята, без никакво увеличение (т.е. zoom=1):



Ясно е, че всички адреси започват с t - няма как да увеличим до някое конкретно квадратче, ако не започнем от самото начало. Ако мислено разделим t на четири равни части, те ще имат адреси съответно tq, tr, ts и tt. Всяка една от тези части представлява отрязък от картата с размер 256х256, при това два пъти по-детайлен от "родителя" t (т.е. zoom=2). Ето илюстрация на принципа:



При квадратчето t картата на цялата Земя е с големина 256х256. Ако сглобим квадратчетата tq, tr, ts и tt, ще имаме карта на цялата земя с големина 512х512, т.е. четири пъти по-голяма. На този принцип можем да адресираме квадратчета на дълбочина до 19 (най-високото увеличение, което съм срещала досега).

Накратко, адресът на всяко парченце от картата представлява някакъв низ от буквите t, q, r и s. Дължината на този низ е равна на нивото на увеличение (zoom, или нивото на детайлност). При най-голямото увеличение, адресът се състои от 19 букви.

Дотук добре. Ако знаем адресът на дадено квадратче, можем да го свалим от някой от Keyhole сървърите на Google (Keyhole или KH е серия оптични американски шпионски сателити, от които идват снимките на Google maps). URL-то, под което могат да се свалят парченцата, е от типа http://kh0.google.de/kh?n=404&v=17&t=trtqstttqrtqqttqqr, където trtqstttqrtqqttqqr е адресът на квадратчето, което търсим.

За да се сдобием с едно подробно изображение на София например, трябва да свалим всички квадратчета, които я изграждат на желаното zoom-ниво. За тази цел най-напред трябва да установим адреса на парчето, от което ще започнем, например горния ляв ъгъл на мозайката. За тази цел Mozilla Firefox върши чудесна работа. Отваряме страницата на Google maps, намираме мястото, от което искаме да започне мозайката, настройваме желаното увеличение, щракваме с десния бутон някъде върху страницата и от контекстното меню избираме "View page info". Отваря се прозорец, в който избираме таб "Media". В този таб можем да видим всички медийни файлове, включени в разглежданата страница. Превъртаме списъка докато стигнем до адреси от типа на http://kh0.google.de/kh?n=404&v=17&t=trtqstttqrtqqttqqr. Преглеждаме ги докато не намерим изображение, което ни харесва за начало на картата и копираме адреса му.

Друг метод е да изчислим адреса на парчето според географските координати на местоположението, което ни интересува и нивото на увеличение, което желаем. Ето един примерен код за целта, написан на JAVA:

public static String getQuadTreeString(double latitude, 
                           double longitude, int zoom){
        //convert to normalized square coordinates
        //use standard equations to map into mercator 
        //projection
 double x = (180 + longitude)/360;
        // convert to radians
 double y = -latitude * Math.PI / 180;
 y = 0.5 * Math.log((1+Math.sin(y)) / 
                                  (1 - Math.sin(y)));
 y *= 1.0/(2*Math.PI);
        // scale factor from radians to normalized
 y += 0.5;
        // and make y range from 0 - 1
 String quad = "t";
        // google addresses start with t
 String lookup = "qrts"; 
        // tl tr bl br
  
 for(int i=0; i    //make sure we only look at fractional part
    x -= Math.floor(x);
    y -= Math.floor(y);
    quad = quad + lookup.charAt((x >= 0.5 ? 1 : 0) 
                                    + (y >= 0.5 ? 2 : 0));
   
    //now descend into that square
    x *= 2;
    y *= 2;
 }
  
 return quad;
}

Остава да изчислим кои квадратчета в каква последователност трябва да подредим, за да сглобим карта при дадени начално квадратче, брой квадратчета по хоризонталата и брой квадратчета по вертикалата. Попаднах на едно много интелигентно решение на този проблем. Основната идея на алгоритъма намерих тук, а конкретна имплементация на PHP може да се свали оттук. Накратко, този метод преобразува адреса, съставен от буквите q, r, s и t в число, върху което в последствие можем да извършваме аритметични операции. Четирите букви изразяват четири различни възможности или състояния. За представянето на чеитири различни възможнисти с двоичен код са ни необходими двуцифрени бинарни числа - 00, 01, 10 и 11. Идеята е да кодираме буквите с тези бинарни числа така, че единият бит (едната цифра на двоичното число) да показва дали квадратчето се намира отгоре или отдолу, а другия бит - дали квадратчето се намира вляво или вдясно. Ако кодираме q=00, r=01, s=11 и t=10 получаваме следната картина:



Бит 0 (дясната цифра) е 0 за квадратчетата, които се намират отляво и 1 за тези, които се намират отдясно. Бит 1 (лявата цифра) е 0 за квадратчетата, които се намират отгоре и 1 за тези, които се намират отдолу.

Ето един пример за адрес, кодиран по този начин:

trtqstttqrtqqttqqr = 100110001110101000011000001010000001

Сега можем да разделим това бинарно число на две равни части - събираме цифрите на четна позиция в едно число и цифрите на нечетна позиция - в друго:

H = 010010000100000001
V = 101011110010011000

Числото H събира в себе си всички нулеви битове, т.е. информацията за стъпките вляво или вдясно, докато навигираме към квадратчето с дадения адрес. По същия начин, числото V събира всички битове, които носят информация за поредните стъпки по вертикалата. Сега, ако искаме да изчилсим адреса на квадратчето, намиращо се непосредствено вдясно от стартовото квадратче, достатъчно е да увеличим числото H с 1, т.е. извършваме стъпка вдясно по хоризонталата (следователно ще получим H = 010010000100000010). За квадратчето непосредствено вляво изваждаме 1. Подхождаме аналогично за движението по вертикалата. Когато сме изчислили новите позиции, достатъчно е да сглобим отново числата H и V в едно цяло число и да преобразуваме отново в буквено кодиране.

За да получим квадратчето, което се намира директно вдясно от стартовото квадратче от примера по-горе, сглобаваме

H = 010010000100000010
V = 101011110010011000

в

100110001110101000011000001010000100

което дава адрес:

trtqstttqrtqqttqrq

Просто и елегантно.

След като разполагах с този алгоритъм, останалото ми се струваше елементарно. Но тук започват същинските проблеми. PHP-скрипът, който цитирах и по-горе, изчислява линковете към сътоветните изображения и ги налепва в една html-таблица. Т.е. в крайна сметка не разполагаме с цялото изображение, а с налепените един до друг отрязъци. Пренаписах скрипта така, че да съставя едно цяло изображение и да връща него като резултат. Проблемът е, че при големи карти, примерно 20х20 квадратчета, PHP процесорът отказва обработката, понеже му се налага да алокира прекалено много памет. Решението тук вероятно би могло да бъде програма като безплатната ImageMagick, макар че не съм пробвала и не мога да гарантирам как се справя с огромни изображения. Вместо това обаче реших да пренапиша всичко в JAVA като използвам JAI (Java Advanced Imaging) и т.нар. TiledImage, което значително намали нужната за обработката памет. За съжаление не намерих начин да запазвам резултатите в JPEG, тъй като явно енкодерът на JPEG все пак в някакъв момент се опитва да алокира памет за цялото изображение наведнъж и паметта не достига. Но TIFF върши чудесна работа, макар да е много по обемист по-размер.

Така или иначе, точно когато всичко проработи, стигнах до същинския проблем: Google, както би било елементарно човек да се досети, е защитил изображенията си срещу масово източване от програми като моята. Първо, ако всеки започне да точи като луд картинка след картинка (а желаещи има много), сървърите ще са претоварени и няма да отговарят достатъчно бързо на хората, които просто ползват картите на Google maps. Второ, снимките на Keyhole хич не са без пари и Google имат добра причина да ги защитят. Така че когато програмата ми започна да работи и да сваля карти от по 90 на 90 парчета, резултатът беше, че Google ми спря достъпа до KH-сървърите. Очевидно имат някакъв черен списък на IP-адресите, които злоупотребяват с картите им. Слава Богу, блокадата трае само няколко часа или ден. Обновяване на IP адреса от провайдера също помага разбира се, но и това не може до безкрай.

Не съм съвсем наясно как функционира защитата, но принципът е гору долу следният. За достъп до сателитните им карти Google са предоставили специално API, т.нар. Google maps API - сбор от JavaScript функции, които могат да бъдат викани от която и да било уеб-страница. Тези функции позволяват вграждане на карта в собствената страница, навигиране в картата, очертаване на полигони, означаване на места и т.н и т.н. За да вгради човек карта на сайта си и да ползва Google maps API трябва да регистрира домейна си безплатно на съответното място. Всеки регистриран домейн получава ключ, който трябва да присъства в кода на всяка страница, която ползва Google maps API. Когато някой потребител отвори уебстраница с вградена карта и регистриран ключ, функциите на Google maps API, използвани на страницата, записват няколко cookies в кеша на браузъра. Едно от тези cookies се изчислява наново за всяка http сесия, така че сравнително бързо се инвалидира. Именно това cookie се използва от браузъра на потеребителя, когато се изпраща запитване до kh-сървърите за парченцата на картата. Убедена съм обаче, че само по себе си едно валидно cookie далеч не е достатъчно за безграничен даунлоуд на снимки. Дори и някоя програма да работи винаги с валидно cookie, сигурна съм, че сървърите на Google чисто и просто спират кранчето, когато усетят нереалистично висок за обичайното потребление брой запитвания от дадено IP.

Въпреки че всичко това ми създаде известни главоболия, трябва да призная, че за пореден път съм очарована от Google. Намерили са много балансирано решение, както винаги - картите и софтуерът им си остават напълно безплатни за ползване, достъпни за всеки и в същото време изображенията са защитени от неправомерно ползване. Разбира се дори и тези механизми не биха спряли някого, който твърдо е решил да източи цялата база данни на keyhole сървърите, но го прави много по-трудоемко и със сигурност подобни случаи не са масово явление. В допълнение, всяко по-детайлно парче от картата минава през филтър, който му добавя ефирен воден знак с логото на Google.

В крайна сметка намерих решение за себе си. По-трудоемко е, но върши работа. Когато си набележа регион, който искам да си изпечатам, най-напред изпразвам кеша на браузъра и после обхождам целия регион в Google maps, в увеличението, което искам. Това гарантира, че всички отрязъци от картата са заредени в кеша (стига размерът му да е достатъчен разбира се). После с програма като cache view извличам всички картинки от кеша и ги копирам в една папка. Намирам началното парче от картата и малката JAVA-програма, която написах, върши останалото. Установих също, че първоначалните ми амбиции за отпечатване на цяла София в най-висок детайл са безсмислени - дори и да съставя толкова огромно изображение (над 500MB в TIFF формат), кой ще го отпечата и върху какво? В крайна сметка ще ми се наложи да го намаля, така че детайлите ще отидат на кино. Така че има смисъл да се съставят карти или на по-ограничени региони, или в по-ниско ниво на увеличение.

Първата поръчка на плакат пристига утре. Да видим...

Edit: Междувременно поръчаният плакат пристигна. Поръчах го при www.fotokasten.de, тъй като вече съм се убедила във високото качество на отпечатъците, които правят. Резултатът е страхотен. При това е страхотен за снимка като тази на София, която в Google Maps излиза доста сивкава и безцветна и имаше нужда от малко пипване във Photoshop. Има толкова по-ярки и детайлни снимки, които само чакат да бъдат отпечатани :D