Using Google Earth as Photo Location Finder

by Gong Liu September 14, 2011 05:19

Introduction

I am an avid hiker. I keep a photolog on Facebook for each of my hikes. The photolog documents places I hiked, things I saw and people I met. The other day when I was compiling my photolog for a recent backpacking trip to Banner Peak in Ansel Adams Wilderness (see a slideshow of the trip at the end of this post), I came across this article on the internet titled "Lonely Grave in the Sierra" by Dr. H. Galic, a professor of Stanford University. The article is about a forgotten memorial to two climbers who died on Banner Peak in the summer of 1934, and how the author relentlessly pursued every lead about the grave, the victims and people involved, and finally put the history puzzle pieces together to recreate the scenario of what happened on that fateful day. Along the way he recounted the history of mountaineering accidents and rescues in High Sierra. It's like an episode of History Detectives, a truly fascinating story.

As much as I enjoy the article I can't help but notice there is no mention about the exact location of the grave. In fact, Dr. Galic has some concerns about it:

"I am intentionally being vague about the exact location of the grave. If you are a genuine hiker or climber, and familiar with the area, you will easily recognize geographical features mentioned in the text. For others, who might see the grave site as a tourist attraction, and plan to come solely for that reason: Please do not bother, you will never find it."  

To me this only raises curiosity. First of all, I didn't know there was a grave before my Banner Peak trip. Now that I've learned about the grave and the story behind it, I really want to know where it is located so I can pay a visit to it next time around. Secondly, I'm a software engineer specialized in digital maps, GPS, and location-based services. I'm obsessed with finding locations. Call it occupational habit. I can't rest without putting the grave's location on a map somehow!  

So what exactly are the geographical features mentioned in the text that may help me locate the grave? Banner Peak, Mt Ritter, Lake Catherine, and Thousand Island Lake are mentioned multiple times in the text. These landmarks help to establish the general area of the grave. So at least I know in which "haystack" I should look for the "needle". Then he mentioned some remote valley where he found the grave on his way to the back side of Mt. Ritter. This helps to narrow down the search further because there are only a few valleys that can be used to access the back side of Mt. Ritter with reasonable effort. But that's pretty much as far as one can go by the text. Fortunately, in the article Dr. Galic included a few photos of the grave with mountains and valleys as backdrop. This makes me think: If a picture is worth a thousand words, is it possible that I can deduce location information from it? Since the grave is rather small, the photos must have been taken in close range. So if I find the location of the photos, I find the grave. 

Incidentally, I'm not the only one who is interested in finding the location of a photo. CIA/NSA is interested in it too! A recent IARPA (Intelligence Advanced Research Projects Activity) Solicitation expresses the desire of wanting a photo location finder. And this news article reveals that the spy agencies' intention is to use the finder to track down terrorists from propaganda photos and videos. I'm sure if such a system is ever developed, my little grave location mystery can be solved with it in a snap of fingers. But before then, before millions of dollars are spent on the project, let me just show you what can be done right now with existing technology.                

Getting the context of a photo 

Before we can find the location of a photo in any outdoor terrain, we need to know its context, such as its general area (country, region, time zone, nearby city, etc.), date/time, and perhaps camera settings. A good place to start for such information is the photo's  Exif (Exchangeable image file format) header. If we are lucky, if the photo happens to be "geotagged", we can get its exact location from the header. There are tools we can use to dump the header and see everything in it. Fig. 1 is a photo taken with a smartphone. What is special about it is that it is geotagged - when the photo was taken, the smartphone's built-in GPS was on and its latitude and longitude coordinates were written to the photo's Exif header. Fig. 2 is a dump of the Exif header. Toward the end of it are the latitude and longitude coordinates. If we upload the photo to an Exif-aware website such as Flickr, we can see the photo's exact location on the map. Please refer to my earlier post for more info about using geotagged photos.  

Fig. 1. A geotagged photo taken with a smartphone. Click to see original. 

Fig. 2. Exif header of above photo. 

Many smartphones are capable of tracking locations by means other than GPS. They use cell towers and WiFi networks for locating aid. The locations obtained this way are not as accurate as GPS, and thus may not be used for geotagging photos that are taken with these smartphones. But they are good enough for providing context information, assuming, of course, we have access to the location data and are able to use it to derive a photo's approximate location based on its time stamp. This article shows a visualization of iPhone location data. It is interesting to note that Apple's location tracking practice caused such an uproar for privacy concerns that Congressional hearings were held. 

Only photos taken with newer generation of digital cameras or smartphones may contain geotags. Most photos don't. Photos that have been edited with photo editing software may lose their original headers. Photos that have been uploaded to some websites (e.g. Facebook) may get their headers trimmed to bare minimum. And then there are software programs that allow a user to remove infomation from a photo's header before publishing. In all these cases we have to derive the context information of a photo from sources other than Exif header. For instance, the most obvious way is to ask the person who took the photo or the publisher who published the photo. Or we may extract that information from the photo's caption or related text, such as the case of our grave site photos. The point is that getting the context of a photo is more of an intelligent work than a software engineering one. Whoever wins the IARPA bid is likely to follow some sort of heuristic approach that incorporates human intelligence into the search algorithm.  

Finding photo location with Google Earth

Assuming we know the context of a photo, how are we going to find its location or the location of an object in the photo? The idea is simple: We'll need a 3D digital ground model, such as Google Earth. We identify some recognizable geographic features from both the photo and the digital model. We try to match the photo's perspective in relation to the geographic features with those in the digital model. We estimate the location of the object visually in the digital model, which yields a location measurement in terms of latitude, longitude, and elevation.

In Fig. 3 the left side is one of the original photos of the grave site by Dr. Galic. Notice that the grave is just a small bronze plaque on top of a pile of rocks. Since I have a rough idea about the general area from the story as well as from my field trip, I can quickly zoom in the area in Google Earth and locate the valley where the grave is supposed to be. With some tweaks I can make Google Earth display a perspective similar to that of the photo in relation to the background mountains, as shown in Fig. 3, the right side. By referencing the grave location in the photo I can mark my best estimate of the location of the grave in Google Earth with a pushpin. The pushpin location measurement can then be read at bottom-center of the Google Earth screen (in the red oval). It's just this simple! 

Fig. 3. Original photo #1 (left) by H. Galic and matched perspective in Google Earth (right). Click to enlarge. 

From this exercise the following points should be noted:

  • We got to appreciate the importance of the context information of a photo. Without it, we wouldn't know where to start. Sifting through all possible mountains, all possible perspectives would be really like finding a needle in a haystack.
  • The matching of the perspective of the photo in Google Earth involves quite a bit tweaking, manually. This is where I see the value of using an automated computer program for the job, as described in the IARPA Solicitation "automated geolocation technologies to work efficiently and accurately over all terrain and large search areas". To be fully automatic, the program must be able to recoganize by itself what key points or features to match between the photo and the digital model, a task that is easy for a human but can be very challenging for a computer.
  • Unlike Google Street View which provides photo realistic environment, Google Earth in rural areas or wilderness areas is only an approximate representation of reality. It lacks the necessary details to identify, for example, the spring and the meadow mentioned in the article, or the rock outcrop in the foreground of above photo. As a 3D model, it is created by interpolating surfaces from survey data points, and thus is limited in accuracy by whatever data source used.  

Because of all the inaccuracy and uncertainty involved from various sources, the photo, the digital model, the underlying data, and human factors, it would be nice to have an estimate of the error of our method. This can be done by having additional observations from either different photos by same observer or same photo by different observers. Observations of same photo by same person are not statistically valid because later oberservations may be influenced by earlier ones. Fig. 4 shows, side by side, a second photo of the grave site by Dr. Galic and a matched perspective in Google Earth, as well as a different estimate of the grave location (the yellow pushpin).

Fig. 4. Original photo #2 (left) by H. Galic and matched perspective in Google Earth (right). Click to enlarge. 

Now we have two observations resulting two estimated grave locations. Based on this data we can establish a set of concentric circular search areas that look like a bull's eye as shown in Fig. 5. The center of the bull's eye is the mid point of the line segment with the two estimated grave locations as end points. The radius of the innermost circle (red) is equal to half of the length of the above line segment. This radius actually represents one standard deviation of the observations in X-Y plane. The radius of the middle circle (yellow) is simply 2 times of the standard deviation, and the radius of the outermost circle (blue), 3 times of that. According to the 3-sigma rule, if the observation follows a normal distribution (it usually does as the error is from multiple independent sources), the probability of finding the grave in the red circle is about 68%, the probability in the yellow circle, 95%, and the probability in the blue circle, 99.7%. In our case, the largest search area (blue) is only about 600 ft across. Conducting a search in it should be quite manageable.

The bull's eye is drawn on a contour map. If we know information about the elevation of the grave, we can narrow down the search further, by searching only an elevation range within the bull's eye.

Note the above error calculation only applies to errors introduced when trying to locate a photo or an object on the photo in a digital model. It does not consider errors in the field, which can only be estimated with field data.   

 

Fig. 5. Bull's eye search areas. Click to enlarge. 

 

Now that I have marked the grave location on the map, I can finally rest easy. But I still have to find the real thing next time I'm there. I have high confidence that I will find it, and when I do I will take a picture of it with my geotagging-capable camera. That's when I will be really, truly satisfied Laughing

Bull's eye calculation for N observations

Let's say we have N observations of the location of an object of interest from a digital model  

(1)

where, xi - longitude, yi - latitude. 

The center of the bull's eye, (μx, μy), can be calculated as follows:

(2)
(3)

The standard deviations of longitude and latitude are given by Equs. 4 and 5, respectively.

(4)
(5)

The radiuses of the three circles, from the smallest to the biggest, can then be calculated as follows:

(6)
(7)
(8)

Slideshow: Banner Peak Expedition

Cheetah Litter Size

by Gong Liu May 02, 2011 19:04

Introduction 

The cheetah is the fastest land animal on the planet. As a runner I can certainly appreciate its speed and gracefulness. I like how the following video explains the cheetah being "The Ultimate Sprinting Machine". While BMW is "The Ultimate Driving Machine", in short distance a cheetah can outrun a BMW due to its extraordinary acceleration.  

Unbelievably as it is, the cheetah is on the brink of extinction and has been on UN's endangered species list since 2008. The other day I watched a TV program about cheetahs and learned that in addition to man-made threats such as habitat loss, human conflict, and poaching, their survival in the wild also suffers from high cub mortality rate due to predation by other carnivores, such as lions, leopards, hyenas, and wild dogs. Up to 90% of cheetah cubs are killed during the early weeks of their lifes. A mother cheetah usually gives birth to a litter of 2 - 5 cubs even though she is capable of producing as many as 9 cubs per litter. This makes me wonder: How do some of the competing factors affect cheetah litter size? Does increasing the average litter size or perhaps decreasing it help the overall cheetah population? Out of pure curiosity I did some preliminary research on the topic and came out the following mathematical model of cheetah litter size.

Cheetah Litter Size Model

A mother cheetah raises her cubs alone. She finds a den for her cubs at a quiet, hidden spot usually in some tall grass, under a low tree, in thick underbrush, or in a clump of rock. She also moves her cubs from den to den every few days to lower the chance of detection by predators. For the first 6 weeks or so, the mother has to leave the cubs alone most of the time, in order to hunt. She may have to travel fairly long distances in search of food. During this time, the cubs are most vulnerable to predation. When a predator does find the cubs in the den, he will kill them all even though he may not eat them all. This overkill behavior is said to be common among predators as a means of eliminating competition. However, whenever the mother is at the den, she will defend her young aggressively and drive away any predators. The cubs emerge from the den at about 6 weeks old and begin to follow their mother to prey-ground. From this time onward, mother and cubs remain inseparable until weaning age. The cubs, though not completely without trouble, will be much safer with the mother than staying in an unguarded den.        

Obviously, the conflict that the mother needs to go out hunting but has to leave her den unguarded from predators determines the well being of her cubs. If she spends less time hunting and guards her cubs at the den, she won't get enough nutrient for herself and her cubs. But if she spends too much time hunting, her cubs may be wiped out by predators while she's gone. Now let's assume that t is the time the mother has to go out hunting and that the probability of the den being visited n times by predators during time t follows a Poisson distribution:

(1)

where,

      λ - the arrival rate of predators at the den

The probability that the entire litter survives is equal to the probability that the den has been visited zero times (n = 0) by predators during time t: 

(2)

We further assume that the entire litter will not survive if the den has been visited at least once by predators. This is just to say that the overkill is 100% effective.

Now let's consider the mother cheetah's total hunting time spent during the cubs' infancy, the critical time period between their birth and their emerging from the den. A mother cheetah is a supreme hunter. However, the food is by no means easy to come by even for her. First of all, she often has to travel long distances from her den to a good prey-ground. Then she has to wait and only hunts at certain time of day to avoid competition from other predators. She only eats fresh meat, which costs more energy to get than scavenging. She has to spend time selecting, stalking and chasing a prey. Her favorite prey is the Thomson's gazelle, which happens to be the second fastest land animal on the planet. Even with an impressive 50% hunting success rate she still comes up empty-handed half of the time. While the actual chasing usually lasts less than a minute, it's so exhausting that she has to rest for up to 30 minutes before she can start eating her catch. During this time, other animals, most notably hyenas, wild dogs and lions may find and take her catch. Even vultures have been known to drive cheetahs from their food. Cheetahs lose up to 50% of their catches to scavengers. A detailed hunting time model that takes all these factors into account can be quite complex. Instead, we'll simply divide the hunting time into two parts, hunting time for the mother herself and hunting time for each cub:       

(3)

where,

      TI - cubs' infancy period, in days
      Th - total hunting time during TI, in hours
      Hm - unit hunting time necessary for the mother's own survival, in hours per day
      Hc - additional unit hunting time for each cub, in hours per day per cub
      L - litter size

Note Hc is a function of time. This reflects the idea that as the cubs grow bigger they will need more milk from the mother, and thus she will have to hunt longer time to maintain her milk supply. Energy in, energy out. For simplicity, we assume Hc is a linear function of time:  

(4)

where,

      hc - rate of additional unit hunting time for each cub, in hours per day per cub per day

and therefore the total hunting time is given by:

(5)

Substitute Equ. (5) into Equ. (2) (Th for t) and we can express the probability of litter survival during infancy in terms of litter size as follows: 

(6)

where,

- total hunting time necessary for the mother's own survival during TI (7)
- total additional hunting time for each cub during TI (8)

Given the odds how would a mother cheetah, or rather her evolutionary instinct, decide the number of cubs to have? Well, let's assume that when it comes to the decision of her litter size, she is risk-neutral (not a risk-averse or risk-taking kind of gal), i.e. her decision is purely based on maximizing the expected value of the number of offsprings that she contributes to the overall cheetah population. We can plot her decision process as the following decision tree:

Fig. 1. Decision Tree for Deciding Litter Size

If she raises no cubs (L = 0), there is simply no contribution to the cheetah population and the species will eventually die out. If she raises L cubs, she faces two possible outcomes: the litter survives (success) and the litter is wiped out (failure). If the litter survives, she contributes L offsprings to the population. If the litter is wiped out, she contributes none. The expected value at the chance node is therefore the expected value of having L surviving cubs:

(9)

Equ. (9) is the objective function to be maximized w.r.t. L. Since we are talking about the average litter size of an average mother cheetah in the cheetah population, L can be treated as a continuous variable. Set the first derivative of Equ. (9) to zero and we can find a single critical point: 

(10)

It is easy to prove that the following second derivative test holds and therefore L* is a maximum point:  

(11)

Equ. (10) simply states that the optimal litter size is in inverse proportion to the arrival rate of predators at the den, λ and to the hunting time for each cub, Tc. If more predators are forced to live close to each other, perhaps due to habitat loss, λ will increase and thus the optimal strategy for the mother cheetah is to have a smaller litter of cubs. Similarly, if the mother has hard time to keep up her milk supply for her cubs due to the lack of prey, which can be caused by a number of factors, such as habitat loss, drought, diseases, etc., then the wise thing for her to do is to have a smaller family. 

Fig. 2 shows E(L) for a given set of parameters. The optimal litter size L* in this case is 2.83 or about 3 cubs.

Fig. 2. Cheetah Litter Size Model 

Cheetah Litter Size Model With Variable TI

One important factor we haven't considered in the previous model is that generally the larger the litter size, the lighter (in body weight) the individual cubs and the longer time they have to stay in the den. I.e. the infancy period is a function of litter size. It has been documented that TI may vary between 5 and 8 weeks. For simplicity, we assume TI is a linear function of L

(12)

where TIa and TIb are some constants. Substitute Equ. (12) into Equ. (5):

(13)

and therefore our objective function can be rewritten as follows:

(14)

Set the first derivative of Equ. (14) to zero and we have the following cubic function of L:

(15)

Equ. (15) has a single real solution:

(16)

when

(17)

where,

(18)
(19)
(20)
(21)
(22)
(23)

The proof of Equ. (16) being a maximum point is too tedious. Instead, we'll just show the following figure of E(L) with variable TI. It obviously has a maximum value and the optimal litter size L* in this case is 1.96 or about 2 cubs. 

Fig. 3. Cheetah Litter Size Model with Variable TI

Comparing Fig. 3 with Fig. 2 we can conclude that the extended infancy period makes the choice of a larger litter size even more undesirable.

Fig. 3 reveals another limiting factor - the maximum hunting time:

(24)

Condition (24) states that the total hunting time in days must be less than infancy period. In other words, the mother cheetah can not hunt 24 hours a day every day for the entire infancy period. This constraint occurs when L > 7.5 cubs in the above example (see Fig. 3). Note Condition (24) is a theoretical constraint. In reality, it ought to be more stringent as the mother really has to spend time nursing her cubs and doing her mothering things.

The mother may not return to her den while she is "waiting" for the best hunting time, which is usually in the early morning or as the sun goes down at the end of the day. There is no point to go back to her cubs if she is hungry and can not produce enough milk. It has been observed in the field that a mother cheetah sometimes has to leave her cubs alone for up to 48 hours to hunt for food. What happens if the mother is so stressed out by the constant pressure to hunt and to meet the ever growing demend from her cubs that she can't handle it? She will abandon them. About 10% cheetah cubs die because of abandonment by their mothers. As cruel as it sounds, abandonment is actually a nature's way to protect the mother so she can start all over again in the next breeding cycle. As the Chinese saying goes, "留着青山在, 不怕没柴烧".

Think for a while, what if cheetahs were humans? One thing for sure their parenting behavior would get them into some serious troubles. First of all, where are the fathers? Are they supposed to step up and be a man? What kind of parents abandon their children? What about leaving children unattended, and not feeding them for hours or even days? Multiple counts of child endangerment and neglect right there. But cheetahs are cheetahs. This is nature. Nature is the ultimate reality show. Triumph and failure, love and cruelty... they are all there for you to see.   

Sensitivity Analysis

One advantage of having a mathematical model is that we can easily test out the impact of parameters of interest.   Fig. 4 and Fig. 5 are generated based on the litter size model with variable TI and the same set of base parameters as Fig. 3. 

Fig. 4. Sensitivity of λ

Fig. 5. Sensitivity of hc

Figs. 4 and 5 show the same pattern - when λ or hc decreases, both L* and E(L*) increase. Remember E(L*) represents the maximum expected value of offspring contribution in one breeding cycle by the mother. She needs to contribute at least 2 offsprings in her entire life in order to maintain current cheetah population. As seen in these figures, unless the conditions are very forgiving (low value of λ or hc), it is hard for her to contribute, in average, even one offspring in a single breeding cycle. This is probably why the species is struggling. However, if she manages to hit the maximum value E(L*) every breeding cycle, she will have better chance to meet her reproductive obligation than otherwise.   

Cheetah Conservation

Now let's exam how the cheetah litter size model may provide insight and guidance in cheetah conservation strategies.

Reducing Man-Made Threats

  • Protect habitat and prey-ground. This is probably the most effective strategy. It has the dual effects of lowering both λ and Tc, and provides ideal environment for cheetahs to boost L* and E(L*).   
  • Stop poaching. Poachers kill cheetahs for their beautiful fur. Then there are trophy hunters killing cheetahs for fun. If a nursing mother cheetah is killed, her cubs will die, and her future breeding potential is gone as well. It's a heavy loss. Part of the effect of poaching can be accounted for as increased λ. After all poachers are predators with guns. Eliminating the market for endangered animal products is an effective way to stop poaching.
  • Resolve human/cheetah conflict. This mainly refers to farmers killing cheetahs to protect their livestock. Same devastating effect as poaching, just for different purpose. Cheetah Conservation Fund (CCF) has been running a successful Livestock Guarding Dog program. It encourages farmers to use specially trained guarding dogs as a non-lethal way to deter cheetahs from preying on livestock.     

Strategies Involving Human Intervention

  • Raise abandoned cubs in a cheetah sanctuary. Abandonment is the second leading cause of cheetah cub high mortality rate. If all abandoned cubs in the wild can be saved, the cub mortality rate can be lowed by about 10%. Finding abandoned cheetah cubs in time can be a challenge. The mother cheetah has to be radio-collared and monitored closely. 
  • Remove some of the competing predators by means of managed hunting. This has same effects as increasing habitat. It lowers the density of predators and thus lowers λ. Fewer predators also mean fewer competitions for prey and thus lower Tc. In addition, the money raised through selling hunting permits by wildlife management authorities can be used for other conservation efforts. It would be an interesting research topic to determine the right level of removal of predators so that certain cheetah population size can be maintained.
  • Optimize cheetah litter size. The basic idea of this strategy is this: Calculate L* for an area based on our litter size model and field data. Survey litter sizes of mother cheetahs in the area. For those mothers who have more cubs than L*, the extra cubs will be removed from them and placed in a cheetah sanctuary. The benefit of this strategy is two-fold. It lightens the load of the mothers affected and gives them a fighting chance to raise their remaining cubs to adulthood. And it serves as a safety net for the mothers by putting some of their cubs under human care to avoid possible total loss in the wild. It is quite possible that the average litter size that was optimized for the environment probably millions of years ago has become less optimized for the current, human-disrupted environment. This strategy may serve as a corrective measure for the disparity. 
  • Establish captive breeding programs. Cheetahs are notoriously difficult to breed in captivity. Only in recent years with the advancement in cheetah reproductive research the captive cheetah population worldwide has seen some growth and is moving toward the goal of self-sustaining (without the need of wild-caught cheetahs). Captive breeding programs will eventually be the last line of defence against cheetah extinction.  

Cheetahs are magnificent animals. They are extremely cute too. They can chirp, as well as meow and purr just like a house cat. Please don't let them die out!

Disclaimer

I'm not a biologist or a cheetah conservationist, just a guy with genuine curiosity about things. The "models" are not verified in any way. 

About

A seasoned computer professional. A tofu culture evangelist...
more >>

Tag Cloud

Calendar

<<  April 2017  >>
MoTuWeThFrSaSu
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

View posts in large calendar
Copyright © 2008-2011 Gong Liu. All rights reserved. | credits | contact me
The content on this site represents my own personal opinions, and does not reflect those of my employer in any way.