-We present an approach for recognizing highlevel geo-temporal phenomena - referred as events/occurrencesfrom in-depth discovery of information, using geo-tagged photos, formal event models, and various context cues like weather, space, time, and people. Due to the relative availability of information, our approach automatically obtains a probabilistic measure of occurrence likelihood for the recognized geo-temporal phenomena. This measure, however, is not only used to find the best event among the merely possible candidates - witnessing the data (including photos), but it can also provide informative cues to human operators in the environments where uncertainty is involved in the existing knowledge.
Sensors have become one of the biggest contributors of BIG DATA datasets. Numerous datasets have been already generated in real-time with rich content, about various information. Mobile wireless devices with multiple sensors like camera and GPS, and internet connectivity, can continuously capture photos and record camera parameters, GPS location, and time. The availability of various web services like MapMyRide 1, and Wunderground 2, provides semantics like ride, and geo-temporal weather status logs, using the captured sensory data. Given that context data exists in massive volumes, an information management paradigm is needed to correlate the information and infer higher level semantics. We propose a technique that automatically correlates various information, and creates a context-aware event graph by combining event models with contextual information related to photos, sensor logs, heterogeneous data sources, and web services. Our technique automatically computes the occurrence-likelihood for the event nodes in the output graph – referred as plausibility measure that provides informative cues to human operators in uncertain environments to make better decisions. Note that this work provides a holistic view of the high-level events witnessed by a dataset; further cause-effect decision-making using the output of this stage in out of the scope of this paper.
Events, in general, are structured and their subevents
have relatively more expressive power [
2http://www.wunderground.com/ event type visit-landmark may have two instances; one instance associated with World War II Memorial and the other to Washington Monument). Consider the following example: A person takes a photograph at an airport less than 1 hour after his flight arrives. To explain this photograph, we first need the background knowledge about the events that generally occur in the domain of a trip. These semantics can only come from an event-ontology that provides the vocabulary for event/entity and event relationships related to a domain. An event-ontology allows explicit specification of models that could be modified using context information to provide very flexible models for high-level semantics of events. We refer to this modification as Event Ontology Extension. It constructs a more robust and refined version of an event-ontology either fully or semiautomatically. Secondly, given the uncertain nature of sensory data (like GPS that is not always accurate), the event type witnessed by the available context data is not decisive; in the above example, the event might either be rent a car, or baggage claim that are two possible conclusions — sometimes no single obvious explanation is available, but rather, several competing explanations exist and we must select the best one. In this work, reasoning from a set of incomplete information (observations) to the most related conclusion out of all possible ones (explanations) is performed through a ranking algorithm that incorporates the plausibility measure; this ranking process is used in Event Ontology Extension.
Problem Formulation: Every input photo has context information (timestamp, location, and camera parameters) and a user. Each photo belongs to a photo stream P of an event with a domain event model O(V, E) –handcrafted by a group of domain experts– whose nodes V are event/entity classes, and edges E represent the relationships between the nodes. There is a bucket B of external data sources represented with a schema. The sources can be queried using the metadata of the input photographs and other available information, including the information about the associated user. Given P , B, O, and information associated to the user, how does one find the finest possible event tag that can be assigned to a photo or a group of similar photos in P ?
Solution: We propose an Event Ontology Extension technique described as follows: select a relevant domain event model through the information related to both P and the user. Using P , B, O, and the user information, infer S – that consists of the best relevant subevent categories to P – where S ✓ V . A member of S is the most plausible event category for a group of contextually-similar photos. For a group of similar p photos cj , a function f calculates the plausibility measure mij for every competing event candidate si: f (si, cj ) = mipj ; this measure indicates how much si is relevant to cj such that cj ⇢ P . Using the information from B, extend S with one or more augmented instances of S, and obtain expressive event tags T . An event tag tie 2 T is a subevent of an event that either exists in O, or can be derived from O such that tie is the finest subevent tag that can be assigned to a group of similar photos. If tie is an assignable tag to any photo, and tie 62 O, we intend to extend O by adding tie to O such that the constraints governing O are preserved. The output is an extension to O that is referred as Or (see fig 1). We argue that attribute values related to an inferred event need to be obtained, refined, and validated as much as possible to create very expressive and reliable metadata. Fig 3 depicts the processing components of our proposed approach. We used semantics such as spatiotemporal attributes/constraints of events, subevent structure, and spatiotemporal proximity. In contrast to machine learning approaches that are limited to the training data set and require an extensive amount of annotation, we propose a technique in which existing knowledge sources are modified and expanded with context information in external data sources including public data sources (like public event/weather directories, local business databases), and digital media archives (like photographs). With this knowledge expansion, new infrastructures are constructed to serve relevant data to communities. Event tags are propagated with event title, place information (like city, category, place name), time, weather, etc. Our proposed technique provides two unique key benefits as follows: 1) A sufficiently flexible structure to express context attributes for events such that the attributes are not hardwired to events, but rather they are discovered on the fly. This feature does not limit our approach to a single data set; 2) leveraging context data across multiple sources could facilitate building a consistent, unambiguous knowledge base.
Some of the main challenges of this work are: a) collecting and correlating information from various sources – we need a general mechanism that automatically queries sources and represents the output; b) a validation mechanism to ensure the coherency of the obtained data; c) currently, publicly available benchmark data sets such as those offered by TRECVid do not suit the purpose of this research (they deal with low level events i.e.,activities). However, higher-level events have relatively more contextual characteristics; d) according to the useful properties of photos, relevant event categories in the model must be discovered. This paper is organized as follows: in section II, we review the prior art that use context and event models for annotating photographs; in section III and IV, we explain our solution strategy; this is followed by section V that demonstrates our experiments, and section VI which is the conclusion.
II.
The important role of context is emphasized in [
III.
Photo’s incomplete information can be improved if
combined with the information related to a group of similar photos.
In this work, two images are similar if they belong to the same
event type. Partitioning a photo stream of an event based on the
context of its digital photographs can create separate subevent
boundaries for its photos [
In this section, we show that it is feasible to go from a set of descriptors D to the best subevent category, when the following conditions are satisfied: (a) the descriptors in D are consistent among themselves, (b) the descriptors in D satisfy subevent categories, (c) axioms of a subevent category are consistently formulated in an event ontology, and (d) the inferred subevent categories are sound and complete.
We use a basic derivation of E* model [
Domain Event Model: A domain event ontology provides specialized taxonomy for a certain domain like trip, see fig 2. The Miscellaneous subevent category in this model is used to annotate the photos that are not matched with any other category. The general vocabulary in a core event model is reused in a domain event ontology. For instance, Parking in fig 2, is a subClassOf of Occurrent (or event) concept in the core event ontology. Also, relationships like subeventOf are reused from the core event ontology. We assume that domain event ontologies are handcrafted by a group of domain experts.
We represent a descriptor using the schema in script
{typed : valued, conf idenced : val}, in which typed, valued,
and val indicate the type, value,and certainty (between 0 and
1) of the descriptor, respectively. For instance, the descriptor
{F lash : ‘of f ‘, conf idence : 1.0} for a photo, states that
the flash was off when the photo was captured with 100%
certainty. Photo and cluster descriptors follow the same
representation model, however the rules for computing the value
of conf idenced are different. We will describe these rules in
the following paragraphs. The descriptor model of a cluster
includes two fields in addition to that of a photo:
plausibilityweight 0 , and implausibility-weight < 0. Later, we will
explain the usage of these fields. All descriptors are either
direct or derived. For photo descriptors, by convention, we
assume that a direct descriptor is straightly extracted from
the EXIF metadata of a photo, and its confidence is 1, as
in the above example. The direct descriptors that we used in
this paper are related to time, location, and optical parameters
of photos like GPSLatitude ,GPSLongitude , Orientation,
Timestamp, and ExposureTime. For a derived descriptor like
{sceneT ype : ‘indoor‘, conf idence : 0.6}, the descriptor
value ‘indoor‘ is computed using direct descriptors like Flash,
through a sequence of computations that extract information
from a bucket of data sources. Some of these descriptors
are PlaceCategory3, Distance4, and HoursOfOperation5. The
confidence score is obtained from the processing unit used
to compute the descriptor value — we developed several
information retrieval algorithms for this purpose,in addition
to the existing tools in our lab [
Given a photo pi in a photo stream P , and the cluster c that groups pi with the most similar photos in P , a processing unit produces the descriptors of c using the descriptors of the photos in c, and more importantly, this process is guided by the descriptors of pi. Every photo in c must support every derived descriptor of pi; such cluster is referred as a sound cluster for pi, and the derived descriptors for c are represented by the distinct union of the derived descriptors of the photos in c. For a derived cluster descriptor d, the value of conf idenced is calculated using the formula in equation 1, in which |c| is the size of the cluster, pj is every photo in c that is represented by d, and g(pj , d) gives the confidence value of d in pj . To find a sound cluster for a photo, the hierarchical structure that is produced by the clustering unit, is traversed using depth-first search — the halting condition for this navigation, if no sound cluster was found, is when current cluster is a leaf node. conf idenced =
X f (pj , d)
(1) 1 c ⇥ | |
Descriptor Consistency: Consistency among a set of descriptors is a mandatory condition to infer the best possible conclusion from it. In this work, consistency must exist among the descriptors of a photo as well as the descriptors of a cluster, using entailment rules described below. (a) vi ! vk: if vi implies vk, then the rules for vk must also be applied to vi. This 3The category of the nearest local business to the coordinates of a photo. 4The distance of a local business to the coordinates of a photo. 5The hours during which a local business is open. is referred as transitive entailment rule. For instance, suppose a photo/cluster has the following description, 0outdoorSeating : true0 ; 0sceneT ype : outdoor0; 0weatherCondition : storm0, which implies that the nearest local business (e.g. restaurant) to the photo/cluster, offers outdoorSeating, and the weather was stormy when the photo(s) were captured. Given the sequence of rules below, outdoorSeating ^ outdoor ! f ineW eather, f ineW eather ! ¬storm rule 2 is entailed that indicates an inconsistency among the descriptors of a photo/cluster.
outdoorSeating ^ outdoor ! ¬storm (2) (b) vi ! f uncremove(vk): vi implies removing the descriptor vk. This is referred as a deterministic entailment rule. (c) vi ^ vk ! truth value: rules of this type are referred as non-deterministic entailment rules in which the inconsistency is expressed by a false truth value e.g. closeShot ^ landscape ! f alse. In that case, further decisions on keeping,modifying, or discarding either of the descriptors vi or vk will be based on the confidence value assigned to each descriptor — this operation is referred as update, which is executed when an inconsistency occurs between two candidate descriptors. The following rules are used by this process: (a) for two descriptors with the same type, the descriptor with lower confidence score is discarded, (b) for two descriptors with different types, the one with lower confidence score gets modified until the descriptors are consistent. The modification is defined as either negation or expansion within the search space. In case of negation, e.g. ¬outdoor ! indoor, the confidence value for indoor descriptor is calculated by subtracting the confidence value of outdoor descriptor from 1. An example of expansion is increasing a window size to discover more local businesses near a location. To avoid falling inside an infinite loop, we limit the count of negation, and the size of search space during expansion, by a threshold. We assign null to the descriptor that has already reached a threshold and is still inconsistent. null is universally consistent with any descriptor. The vocabulary that is used to model the descriptors for a photo/cluster is taken from the vocabulary that is specified in the core event model.
C. DATA SOURCES
We represent each data source with a declarative schema, by using the vocabulary of the core event model. This schema indicates the type of source output. In addition, it specifies what type of the input attributes a source needs, to deliver the output. Data sources are queried using the SPARQL language6. A query is constructed automatically using the schema of data sources, and the available information. Simply put, a source is selected if its input attributes match the available information I. At every iteration, I is incrementally updated with new data that is delivered by a source. The next source is selected if its input attributes are included in I. This process continues until no more source with matching attributes is left in the bucket B.
6http://www.w3.org/TR/rdf-sparql-query/
From a set of consistent cluster descriptors (observations), we developed a context discovery algorithm to infer the most plausible subevent category described in a domain event ontology. This algorithm, uses the domain event model, which is a graph; we represent this graph with the notation O(V, E) in which V includes event classes, and E includes event relationships. Traversing the event graph O starts with the root of hierarchical subevent structure. The algorithm visits event candidates in E through some of the relationships in E like subeventOf, co-occurring-with, co-located-with, spatiallynear, temporal-overlap, before, and after — these relationships help to reach other event candidates that are in the spatiotemporal neighborhood of an event. An expandable list, referred as Lv, is constructed from E, to maintain the visited event/subevent nodes during an iteration i — if an event is added to Lv, it cannot be processed again during the extent of i. At the end of each iteration, Lv is cleared. In every iteration, the best subevent category is inferred through a ranking process, from a set of consistent observations.
To find the most plausible subevent category, we introduce p Measure of Plausibility (mij ) to rank event candidates. This measure is computed using two parameters (1) granularity score (wg), and (2) plausibility score (wAX ). wg is equivalent to the level of the event in the subevent hierarchy in the domain event ontology. To compute wAX , we used ’plausibilityweight’ (w+) and ’implausibility-weight’ (w ) which are two fields of a cluster descriptor. The value of w+ is equal to the confidence value assigned to a descriptor, and the value of w is equal to w+. If a descriptor could not be mapped to any event constraint, wAX remains unchanged. If a descriptor with w+ = ↵ satisfies an event constraint, then w+ is added to wAX , otherwise, w is added to wAX (i.e., wAX = wAX ↵ ). The only exception is for the cluster descriptors time-interval and boundingbox; if either one of these descriptors satisfies an explanation, then w+ = 1; in the opposite case, w 100 — when a cluster has no overlap with the spatiotemporal extent of an event si, w 100 makes si the least plausible candidate in the ranking. According to the formula in III-D, wAX also depends on the fraction of satisfied event constraints; N is the total number of constraints for an event candidate. wAX = N1 X wAjX , 1 j N (3)
Finally, we use the following instructions to compare two event candidates e1 and e2: when e1 is subsumed by e2, mipj for each event candidate is normalized using the formula in equation 4, in which ei ⌘ e1 and ej ⌘ e2, otherwise, ei.mij = ei.wAX . The candidate with the highest mipj is the p most plausible subevent category.
p ei.mij =
ei.wAX max(ei.wAX , ej .wAX ) +
ei.wg max(ei.wg , ej .wg ) (4) When a subevent category is inferred from a set of observations, it will not be considered again as a candidate for the next set of observations. Event inference halts if no more subevent category is left to be inferred from the domain event ontology.
EXTENSION: The inferred subevent categories E0 are refined with the context data extracted from data sources in the bucket B, through the refinement process. First, let us elaborate this process by introducing the notion of seed event, which is an instance of an inferred category in E0, which is not yet augmented with information. An augmented seed-event is an expressive event tag. The seed-event is continuously refined with information from multiple sources.
Our extension algorithm uses a similar strategy as what we used in subsection III-C. The difference is, the attributes of a data source at each iteration is supplemented by the user information and the attributes of a seed-event (I ) that is represented with the same schema that is described in the event ontology. Given a sequence of input attributes, if a data source returns an output-array of size K, then our algorithm creates K new instances of events with the same type as in the seed-event, and augments them with the information in the output-array. The augmented seed-events are added to I for the next iteration; I is constantly updated until all the event categories in E0 are augmented, and/or there is no more data source (in the bucket B) to query. To avoid falling into an infinite loop of querying data sources, we set the following condition: a data source cannot be queried more than once for each seed-event. We defined some queries manually that are expressed through the relative spatiotemporal relationships in the event ontology, and the augmented seed-events; these queries are used to augment the seed-events with relative spatiotemporal properties. When a seed-event gets augmented with information, our technique validates the event tag by using the event constraints, augmented event attributes, and a sequence of entailment rules that specify the cancel status for an event. For instance, if the weather attribute for an event is heavy rain, and the weather constraint fine weather is defined for an event, then the status of the event tag becomes canceled. After the validation, event tags are added to the domain event ontology by extending event classes through typeOf relationship. This step produces an augmented event ontology that is the extended version of the prior model (see fig 1).
FILTERING
Filtering is a two-step process; (1) redundant and irrelevant clusters are pruned from the hierarchical cluster structure produced by the clustering component, see fig 4-step-1. (2) filter redundant photos from the matched cluster, see fig 4step-2. This is accomplished by applying the context and visual constraints of the expressive tag that is matched to the cluster. We used a concept verification tool7 to verify the visual constraints of events using image features. This tool uses pyramids of color histogram and GIST features. Filtering operation is deeply guided by the expressive tags. During this operation, subevent relations are used for navigating the augmented event model.
We focused on 3 domain scenarios vacation, professional trip, and wedding. We crawled Flickr, Picasaweb, and our lab data sets. We observed that many people store their personal photos according to events; accordingly, we collected the data sets based on time, space, and event types (like travel, conference, meeting, workshop, vacation, and wedding). We developed some crawlers to download about 700 albums of the day’s featured photos; we crawled photo albums created since the year 2010 since most of the older collections did not contain geo-tagged photos. After 4 months, we collected 570 albums (about 60K photos) which had the required EXIF information containing location, timestamp, and optical camera parameters. We ignored the albums a) smaller than 20 photos, b) with non-English annotations. The average number of photos per album was 105. We used the albums from the most 7http://socrates.ics.uci.edu/Pictorria/public/demo active users based on the amount of user annotations, ending up with a collection of 20 users with heterogeneous photo albums in terms of time period and geographical sparseness. The geographic sparseness of albums ranged from being across continents, to cities of the same country/state (see fig 5). We noticed that data sources do not equally support all the geographic regions; e.g., only a small number of data sources supported the data sets captured inside India. The photos for vacation/professional-trip domains have higher temporal and geographical sparseness compared to photos related to wedding domain. The number of albums for vacation domain exceeds the other two.
Experimental Set-Up set, while providing them with three domain event models. For the non-lab data set, the ground truth provides a manual and subjective event labeling done by the very owner of the data set being unaware of the experiments. Because of the subjective nature of the non-lab data set, the event types that were not contained in the event domain ontology are replaced with event type miscellaneous that is an event type in every domain event ontology in this work. For each experiment, we compute standard information retrieval measures (precision, recall, and F1-measure), for the event types used in tags. In addition to that, we introduce a measure of correctness for event tags. The score is obtained based on multiple context cues. For instance, label meeting with Tom Johnson at RA Sushi Japanese Restaurant in Broadway, San Diego, during time interval ”blah” in a sunny day, in an outdoor environment, specifies type of the event, its granularity in the subevent hierarchy, place, time, and environment condition. We developed an algorithm that evaluates each cue with a number in the range of 0 to 1 as follows: 1) event type: wrong = 0, correct = 1, somehow correct = LLTpP such that Lp is the subevent-granularity level for a predicted tag and LT P is the subevent granularity level for the true-positive tag (the predicted tag is the direct or indirect superevent of the truepositive tag i.e., LLTpP 1); 2) place: includes place name, category and geographical region. If the place name is correct, score 1 is assigned and the other attributes will not be checked. Otherwise, 0 is assigned; for the category and/or geographical region if correct, score 1 is assigned, and 0 otherwise. The average of these values represent the score for place; 3) for weather, optical, and visual constraint: wrong=0, correct =1, unsure = 0.5; 4) time interval: if the predicted event tag occurs anytime during the true-positive event tag, 1 is the score, otherwise 0. The average of the above scores represents the correctness measure for a predicted event tag. We introduce average correctness of annotation that is calculated using the formula in equation 5, where wj is the score for the jth predicted tag, and L is the total number of expressive event tags detected by our approach.
PL j=1 wj
L correctness = ; context = 1
Err (5)
We picked the 4 most active users (based on the amount of user annotation) from our non-lab, downloaded data set, and 2 most active users from our lab data set (based on the number of collections they own). As ground-truth for the lab data set, we asked the owners to annotate the photos using their personal experiences, and an event model that best describes the data The metric context in equation 5 is used to measure the average context provided by data sources for annotating a photo stream; parameter Err is the average error related to the information provided by data sources used for annotating a photo stream (0 Err 1); the following guidelines are applied automatically, to measure this value: (a) if the information in a data source is related to the domain of a photo stream, but it is irrelevant to the context of the photo stream, assign error-score 1. For instance, data source TripAdvisor returns zero results related to Things-To-Do for the country at which a photo stream is created. Also, if a photo stream for a vacation trip does not include any picture taken in any landmark location, TripAdvisor does not provide any coverage; (b) assign error-score 0 if the type of a source is relevant as well as its data (i.e. non-empty results); (c) if the data from a relevant source is insufficient for a photo stream, assign errorscore 0.5. For instance, only a subset of business venues in a region are listed in data source Yelp; as a result, the data source returns information for less than 30% of the photo stream; (d) for a data source, multiply the error-score by a fraction in which the numerator is the number of photos tagged using this data source, and the denominator is the size of the photo stream. Do this for all the sources and obtain the weighted average of the error-scores. The result is Err. The implication of our result in fig 6 is as follows: while the correctness of event tags (for a photo stream of an event) peaks with the increase in context, relatively, smaller percentage of photos are tagged using non-miscellaneous events, and larger percentage of photos are tagged using miscellaneous event. This means if the suitable event type for a group of photos does not exist in an event ontology, the photos are not tagged with an irrelevant non-miscellaneous event; instead, they are tagged with miscellaneous event which means other. The right side of the figure indicates that even though the number of miscellaneous and non-miscellaneous event tags does not change, the correctness is still increasing; this means that the tags get more expressive since more context cues are attached to them. The quality of annotations is increased when more context information is available. This shows that event ontology by itself is not as effective as augmented event ontology. We demonstrate three classes of experiments in table I. This table shows the average values (between 0 to 1) for the measure metrics discussed earlier (precision, recall, F1, correctness). We use the work proposed in (Paniagua, 2012) as a baseline. It is based on space and time to detect event boundaries in conjunction with using English album descriptions. This baseline approach, with F1-measure about 0.6 and correctness of almost 0.56, illustrates that time and space are important parameters to detect event boundaries. On the other hand, the baseline approach is limited to using only spatiotemporal containment for detecting subevent hierarchy, it does not support other types of relationships among events (like co-occurring events, relative temporal relationships) and other semantic knowledge about the structure of events. Also, it requires human-induced tags which are noisy. For the second set of experiments, we use an event domain ontology without augmenting it with context information. This approach gives worse results since the context information is disregarded during detecting event boundaries. It provides the F1-measure of almost 0.32 and correctness of 0.13. Our last experiment leverages our proposed approach, and achieves F1-measure of about 0.85, and correctness of 0.82. Compared to our baseline approach, we obtain about 26% improvement in the quality of tags which is a very promising result.
The running time for our proposed approach, and visual concept verification is shown in fig 7, which illustrates the results for data sets of two sources i.e., lab, and non-lab (including Flickr, and Picasaweb), and three event domains.
Cross-Domain Comparison : In general, we found smaller number of context sources for wedding data sets compared to the other two domains; as a result, the extension process exits relatively faster, and the running time for the concept verification process increases. We observed the correctness of event tags degrades when Event Ontology Extension process exists fast. This observation confirms the findings of fig 6.
Cross-Source Comparison: Within each domain, we compared the cpu-performance among lab and non-lab data sets; Event Ontology Extension exits relatively faster for non-lab data sets. The justification for this observation is that we could obtain user-related context like facebook events/check-ins from our lab users (U3, U4), but such information was missing in the case of non-lab data sets. This absence of information impacts wedding data sets the most, since the context information in the wedding scenario largely includes personal information such as guest list, and wedding schedule that are not publicly available on photo sharing websites. In professionalTrip scenario, this impact is smaller than wedding, and larger than vacation; the missing data is due to the lack of context information related to personal meetings, and conference schedules. In vacation scenario, data sources are mostly public; only a small portion of context information comes from the user-related context such as flight information,and facebook check-ins; therefore, we did not find a significant change in the cpu-time between lab and non-lab data sets.
VI.
CONCLUSIONS
Our proposed technique addresses a broad range of research challenges to achieve a powerful event-based system that can adapt to different scenarios and applications like
RESULTS FOR AUTOMATIC PHOTO ANNOTATION FOR THE
DATA SETS OWNED BY THE 5 MOST ACTIVE USERS. those in intelligence community, multimedia applications, and emergency response. This is the starting step for combining complex models with BIG DATA.