Tuesday, June 07, 2011

Readers' Mailbag: ICASSP Tutorial, Gigapixel Binary Sensing, Perceptual Hashes, E.Coli outbreak and Cell phone data

Zhilin Zhang let me know of his advisor's ICASSP 2010 Tutorial slides: Sparse Signal Recovery: Theory, Applications and Algorithms by Bhaskar Rao and DavidWipf.

I have seen quite a few presentations on compressive sensing, but I think this picture quite beautifully explains what compressive sensing is to people who have done transform coding all their lives (wavelets, DCT...)

Yue Lu let me know that this is not compressed sensing but that it might be interesting, and sure enough it is: Gigapixel Binary Sensing: Image Acquisition Using Oversampled One-Bit Poisson Statistics by Feng Yang, Yue M. Lu, Luciano Sbaiz, Martin Vetterli. The abstract reads:
We study a new gigapixel image sensor that is reminiscent of traditional photographic film. Each pixel in the sensor has a binary response, giving only a one-bit quantized measurement of the local light intensity. To analyze its performance, we formulate the oversampled binary sensing scheme as a parameter estimation problem based on quantized Poisson statistics. We show that, with a single-photon quantization threshold and large oversampling factors, the Cram\'{e}r-Rao lower bound (CRLB) of the estimation variance approaches that of an ideal unquantized sensor, that is, as if there were no quantization in the sensor measurements. Furthermore, the CRLB is shown to be asymptotically achievable by the maximum likelihood estimator (MLE). By showing that the log-likelihood function of our problem is concave, we guarantee the global optimality of iterative algorithms in finding the MLE. Numerical results on both synthetic data and images taken by a prototype sensor verify our theoretical analysis and demonstrate the effectiveness of our image reconstruction algorithm. They also suggest the potential application of the oversampled binary sensing scheme in high dynamic range photography.
Some aspect of this work resemble that of epsilon-photography but I cannot help remember this story of the airy disk making a point and click camera was a compressive sensing system (see also weak compressive sensing).

Serguey Ten has his thoughts of perceptualashes and he is sharing them on twitter. While Eric Tramel wants to look into a simple implementation of this CSHash. 

On the cell phone tracking for the E.coli outbreak, I received the following comments:

Peter is asking:
Igor, I'm curious, I haven't heard of anyone even asking for (or denying) the analysis of cell phone data. Do you have a reference? Google is not helping me because EHEC collides with the "cell phones = brain cancer" story... 
I am merely suggesting that the data should be used and since I haven't heard anything about it in the media, I am expecting that nobody has really used them even though they are still available. In particular I would be very surprised if they collected that data of the non-residents since there is no European framework for that.

Tim rightly mentions the following point:

Using the mobile data to track individuals movements would partly be dependent upon the handset (3G iPhone, android etc) that supports location based services. With luck there will be many small packets of data for email or some data application. This would provide many frequent data points you could use to track detailed individual movements, say every 20 mins. If only voice calls and SMS/text are used, then there will be fewer points of data to work with and you will likely need many thousands of individuals (rather than 500) to build detailed insight.

What you describe is definitely a good idea, and not dissimilar to marketing analytics the telco might do themselves.

Cheers

http://timmanns.blogspot.com/

Yes getting the information directly from the handset might definitely be interesting as the data is in the owner's hand as opposed to giving permission to the German Telco. But I worry that not everybody has the latest GPS/smartphones. Still this is interesting.

In the meantime, it looks like the beansprouts are not the culprit so we are back to square one while the cell phone data still haven't been used. The Spaniards now think Germany owes them more than 200 million euros. Let me restate: if the outbreak was spread because of second hand contact none of these questionnaires and traditional epidemiology means are going to work. The cell phone data are our only way to get some idea as to where this is coming from.



Thanks Zhilin, Yue, Eric, Serguey, Tim and Peter!

Monday, June 06, 2011

Are Perceptual Hashes an instance of Compressive Sensing ?

On Hacker News, iandanfortth wondered if perceptual hashes were related to compressed sensing. The answer is, I think, yes. What are perceptual hashes ? according to the web page:

Perceptual hash algorithms describe a class of comparable hash functions. Features in the image are used to generate a distinct (but not unique) fingerprint, and these fingerprints are comparable.

Perceptual hashes are a different concept compared to cryptographic hash functions like MD5 and SHA1. With cryptographic hashes, the hash values are random. The data used to generate the hash acts like a random seed, so the same data will generate the same result, but different data will create different results. Comparing two SHA1 hash values really only tells you two things. If the hashes are different, then the data is different. And if the hashes are the same, then the data is likely the same. (Since there is a possibility of a hash collision, having the same hash values does not guarantee the same data.) In contrast, perceptual hashes can be compared -- giving you a sense of similarity between the two data sets.

A more robust algorithm is used by pHash. (I use my own variation of the algorithm, but it's the same concept.) The pHash approach extends the average approach to the extreme, using a discrete cosine transform (DCT) to reduce the frequencies.
  1. Reduce size
  2. . Like Average Hash, pHash starts with a small image. However, the image is larger than 8x8; 32x32 is a good size. This is really done to simplify the DCT computation and not because it is needed to reduce the high frequencies.
  3. Reduce color
  4. . The image is reduced to a grayscale just to further simplify the number of computations.
  5. Compute the DCT
  6. . The DCT separates the image into a collection of frequencies and scalars. While JPEG uses an 8x8 DCT, this algorithm uses a 32x32 DCT.
  7. Reduce the DCT
  8. . This is the magic step. While the DCT is 32x32, just keep the top-left 8x8. Those represent the lowest frequencies in the picture.
  9. Compute the average value
  10. . Like the Average Hash, compute the mean DCT value (using only the 8x8 DCT low-frequency values and excluding the first term since the DC coefficient can be significantly different from the other values and will throw off the average). Thanks to David Starkweather for the added information about pHash. He wrote: "the dct hash is based on the low 2D DCT coefficients starting at the second from lowest, leaving out the first DC term. This excludes completely flat image information (i.e. solid colors) from being included in the hash description."
  11. Further reduce the DCT
  12. . This is the magic step. Set the 64 hash bits to 0 or 1 depending on whether each of the 64 DCT values is above or below the average value. The result doesn't tell us the actual low frequencies; it just tells us the very-rough relative scale of the frequencies to the mean. The result will not vary as long as the overall structure of the image remains the same; this can survive gamma and color histogram adjustments without a problem.
  13. Construct the hash
  14. . Set the 64 bits into a 64-bit integer. The order does not matter, just as long as you are consistent. To see what this fingerprint looks like, simply set the values (this uses +255 and -255 based on whether the bits are 1 or 0) and convert from the 32x32 DCT (with zeros for the high frequencies) back into the 32x32 image: = 8a0303769b3ec8cd
  15. At first glance, this might look like some random blobs... but look closer. There is a dark ring around her head and the dark horizontal line in the background (right side of the picture) appears as a dark spot.


The differences with traditional Compressed Sensing are minimal in fact, but the algorithm is in line with some of the work undertaken in manifold signal processing, LSH, random projection etc. The differences are: 
  • The proposed hash is deterministic, generally in Compressed Sensing, you want to rely on random projections in order to get some sort of universality and by the same token some sort of robustness. The random nature of the projection is preferred but not a necessary condition as there are some results for deterministic compressive sensing problems.
  • Step 3 and 4 are the most fascinating steps because they are clearly one of the approaches used in manifold signal processing for images. In short, because the image manifold is non differentiable you really want to defocus the pictures so that similar images become neighbors in the now smooth image manifold (in the pHash implementation you just use the low frequency component of the image). The defocusing idea in compressive sensing was, for instance, featured in Mike Wakin's PhD thesis and attendant papers.  
  • For one image, the hash consists of 16 measurements (16 bits of the hash result). So to a certain extent this is achieving some sort of compression. But this has to be weighted against the fact that the algorithm is already lossy as the initial size and color of the picture are lost forever after step 1 and 2. This information loss brings us to the next point.
  • Step 6 also loses some information, however, it is very similar to some CS "lossy" schemes such as the 1-bit compressed sensing approach (there you retain only the sign of the measurement). Let us mention the use of 1-bit scheme in a previous entry on seismic noise this week-end) 

All in all, I am not overly surprised that this algorithm works and it looks very easy to implement.  Compressive sensing could probably provide faster and more robust ways to encode images. Why you ask ? Because:

  • the random mixing of DCT components makes the measurement pretty robust
  • the redundancy brought by the use of all colors makes the hash robust to comparison between similar scenes with different colors (do we care about hair color feature ?)

The other fascinating aspect of the pHash algorithm is that it probably works because the underlying image is sparse in the DCT basis. However, nothing in the algorithm hints on that, it just works. I have not tried it but this is how a CSHash would work:
  • Step 1: Same as pHash step 1
  • Step 2: Keep the colors
  • Step 3: Blur the image (with a gaussian kernel for instance) and remove average value from the image for each color
  • Step 4: Make your three color image into one large vector (size is 32x32x3 = 3072) , and multiply that vector with a 16 x 3072 rectangular random Gaussian matrix  (this same matrix needs to be used for all the photos you want to analyze/compare.)
  • Step 5: Take the most important bit of each element of the new vector (of size 16).
  • Step 6: Same as pHash step 7.
One advantage of this algorithm is that it is specific to this implementation since one choose a random Gaussian matrix in the algorithm. In other words, you have your own encryption algorithm and your database of hash cannot be guessed easily. It might even happen that a specific random matrix does a better job on specific type of images specific to your collection. Finally, since the encoding is pretty universal, it can directly be applied to movies as well.

Related posts:

Compressive Sensing Literature This Week

Today, we have a few papers and a talk. enjoy.

Compressed sensing with preconditioning for sparse recovery with subsampled matrices of Slepian prolate functions by Laurent Gosse. The abstract reads:
Efficient recovery of smooth functions which are s-sparse with respect to the base of so–called Prolate Spheroidal Wave Functions from a small number of random sampling points is considered. The main ingredient in the design of both the algorithms we propose here consists in establishing a uniform L∞ bound on the measurement ensembles which constitute the columns of the sensing matrix. Such a bound provides us with the Restricted Isometry Property for this rectangular random matrix, which leads to either the exact recovery property or the “best s-term approximation” of the original signal by means of the ℓ1 minimization program. The first algorithm considers only a restricted number of columns for which the L∞ holds as a consequence of the fact that eigenvalues of the Bergman’s restriction operator are close to 1 whereas the second one allows for a wider system of PSWF by taking advantage of a preconditioning technique. Numerical examples are spread throughout the text to illustrate the results.


Suppose a given observation matrix can be decomposed as the sum of a low-rank matrix and a sparse matrix, and the goal is to recover these individual components from the observed sum. Such additive decompositions have applications in a variety of numerical problems including system identification, latent variable graphical modeling, and principal components analysis. We study conditions under which recovering such a decomposition is possible via a combination of `1 norm and trace norm minimization. We are specifically interested in the question of how many sparse corruptions are allowed so that convex programming can still achieve accurate recovery, and we obtain stronger recovery guarantees than previous studies. Moreover, we do not assume that the spatial pattern of corruptions is random, which stands in contrast to related analyses under such assumptions via matrix completion.

Group Sparsity with Overlapping Partition Functions by Gabriel Peyré, Jalal Fadili. The abstract reads:
This paper introduces a novel and versatile group sparsity prior for denoising and to regularize inverse problems. The sparsity is enforced through arbitrary block-localization operators, such as for instance smooth localized partition functions. The resulting blocks can have an arbitrary overlap, which is important to reduce visual artifacts thanks to the increased translation invariance of the prior. They are moreover not necessarily binary, and allow for non-integer block sizes. We develop two schemes, one primal and another primal-dual, originating from the non-smooth convex optimization realm, to efficiently solve a wide class of inverse problems regularized using this overlapping group sparsity prior. This scheme is flexible enough to handle both penalized and constrained versions of the optimization problems at hand. Numerical results on denoising and compressed sensing are reported and show the improvement brought by the overlap and the smooth partition functions with respect to classical group sparsity.

Genome-wide association studies have successfully identified hundreds of novel genetic variants associated with many complex human diseases. However, there is a lack of rigorous work on evaluating the statistical power for identifying these variants. In this paper, we consider the problem of sparse signal identification in genome-wide association studies and present two analytical frameworks for detailed analysis of the statistical power for detecting and identifying the disease-associated variants. We present an explicit sample size formula for achieving a given false non-discovery rate while controlling the false discovery rate based on an optimal false discovery rate procedure. The problem of sparse genetic variants recovery is also considered and a boundary condition is established in terms of sparsity and signal strength for almost exact recovery of disease-associated variants as well as nondisease-associated variants. A data-adaptive procedure is proposed to achieve this bound. These results provide important tools for sample size calculation and power analysis for large-scale multiple testing problems. The analytical results are illustrated with a genome-wide association study of neuroblastoma.

We consider the following k-sparse recovery problem: design an m × n matrix A, such that for any signal x, given Ax we can efficiently recover ˆx satisfying kx − xˆk1 ≤C mink-sparse x′ kx − x′k1 . It is known that there exist matrices A with this property that have only O(k log(n/k)) rows. In this paper we show that this bound is tight. Our bound holds even for the more general randomized version of the problem, where A is a random variable, and the recovery algorithm is required to work for any fixed x with constant probability (over A).



Generating Functional Analysis of Iterative Algorithms for Compressed Sensing by Kazushi Mimura. The abstract reads:
It has been shown that approximate message passing algorithm is effective in reconstruction problems for compressed sensing. To evaluate dynamics of such an algorithm, the state evolution (SE) has been proposed. If an algorithm can cancel the correlation between the present messages and their past values, SE can accurately tract its dynamics via a simple one-dimensional map. In this paper, we focus on dynamics of algorithms which cannot cancel the correlation and evaluate it by the generating functional analysis (GFA), which allows us to study the dynamics by an exact way in the large system limit


On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions by J. Bailey
Mark Iwen, C. V. Spencer. The abstract reads:
We present a general class of compressed sensing matrices which are then demonstrated to have associated sublinear-time sparse approximation algorithms. We then develop methods for constructing specialized matrices from this class which are sparse when multiplied with a discrete Fourier transform matrix. Ultimately, these considerations improve previous sampling requirements for deterministic sparse Fourier transform methods.


Reconstruction of Fractional Brownian Motion Signals From Its Sparse Samples Based on Compressive Sampling by Andriyan Bayu Suksmono. The abstract reads:
This paper proposes a new fBm (fractional Brownian motion) interpolation/reconstruction method from partially known samples based on CS (Compressive Sampling). Since 1/f property implies power law decay of the fBm spectrum, the fBm signals should be sparse in frequency domain. This property motivates the adoption of CS in the development of the reconstruction method. Hurst parameter  H that occurs in the power law determines the sparsity level, therefore the CS reconstruction quality of an fBm signal for a given number of known subsamples will depend on  H. However, the proposed method does not require the information of H to reconstruct the fBm signal from its partial samples. The method employs DFT (Discrete Fourier Transform) as the sparsity basis and a random matrix derived from known samples positions as the projection basis. Simulated fBm signals with various values of H are used to show the relationship between the Hurst parameter and the reconstruction quality. Additionally, US-DJIA (Dow Jones Industrial Average) stock index monthly values time-series  are also used to show the applicability of the proposed method to reconstruct a real-world data.


A well-known analysis of Tropp and Gilbert shows that orthogonal matching pursuit (OMP) can recover a ksparse n-dimensional real vector from m = 4k log(n) noisefree linear measurements obtained through a random Gaussian measurement matrix with a probability that approaches one as n → ∞. This work strengthens this result by showing that a lower number of measurements, m = 2k log(n − k), is in fact sufficient for asymptotic recovery. More generally, when the sparsity level satisfies kmin ≤ k ≤ kmax but is unknown, m = 2kmax log(n − kmin) measurements is sufficient. Furthermore, this number of measurements is also sufficient for detection of the sparsity pattern (support) of the vector with measurement errors provided the signal-to-noise ratio (SNR) scales to infinity. The scaling m = 2k log(n − k) exactly matches the number of measurements required by the more complex lasso method for signal recovery with a similar SNR scaling.


Adaptive compressive learning for prediction of protein-protein interactions from primary sequence by Ya-Nan Zhang  Xiao-Yong Pan, Huang Y, Hong-Bin Shen. The abstract reads:
Protein-protein interactions (PPIs) play an important role in biological processes. Although much effort has been devoted to the identification of novel PPIs by integrating experimental biological knowledge, there are still many difficulties because of lacking enough protein structural and functional knowledge. It is highly desired to develop methods based only on amino acid sequences for predicting PPIs. However, sequence-based predictors are often struggling with the high-dimensionality causing over-fitting and high computational complexity problems, as well as the redundancy of sequential feature vectors. In this paper, a novel computational approach based on compressed sensing theory is proposed to predict yeast Saccharomyces cerevisiae PPIs from primary sequence and has achieved promising results. The key advantage of the proposed compressed sensing algorithm is that it could compress the original high-dimensional protein sequential feature vector into a much lower but more condensed space taking the sparsity property of the original signal into account. What makes compressed sensing much more attractive in protein sequence analysis is its compressed signal can be reconstructed from far fewer measurements than what is usually considered necessary in traditional Nyquist sampling theory. Experimental results demonstrate that proposed compressed sensing method is powerful for analyzing noisy biological data and reducing redundancy in feature vectors. The proposed method represents a new strategy of dealing with high-dimensional protein discrete model and has great potentiality to be extended to deal with many other complicated biological systems.


Parallel Computation Toolbox for PC-Based Medical Image Reconstruction by Ahmed Abdel Salam, Norhan Ahmed Shaker, Fadwa Fawzy Fouad, and Yasser M. Kadah. The introduction reads:
Magnetic resonance imaging (MRI) has been used extensively for clinical purposes to depict anatomy because of its non-invasive nature to human body. It is always desirable to enhance the resolution of MR images in order to confirm the presence of any suspicious behavior inside the body while keeping the imaging time short. At present, MR imaging is often limited by high noise levels, significant imaging artifacts and/or long data acquisition (scan) times [1]. Advanced image reconstruction algorithms can mitigate these limitations and improve image quality. In this paper we aim to enhance image quality and shorten imaging time using Compressed sensing (CS) and parallel computing techniques.

Finally, there is a talk this week at University of Bonn, Hard Thresholding Pursuit: an algorithm for compressive sensing by Barbara Fuchs.

Sunday, June 05, 2011

Lessons from the German E.Coli outbreak so far.

According to ITN News in England, the E.Coli outbreak in Germany may have been traced back to beansprouts produced in Germany.

As an outsider, this news raises several points that something's gotta give:

- The majority of German people might be against anything related to nuclear energy but one of the easiest way to reduce the probability of a future outbreak (including those with wilfull intent) is probably to go for a food irradiation program. I realize this is probably not going to fly with a lot of the beansprouts customers, but adhering to guidelines is just not an active prevention policy.

- The outbreak started around May 5th. It's been a month and 18 people have died in horrible conditions. More than 2000 people are sick (and they can't be given antibiotics). In short, this was a crisis early on and some misconception about privacy is essentially harming people. While privacy is a cherished matter especially in Germany, there should be a middle ground when folks are willing to give away their cell phone records instead of relying on necessarily incomplete oral surveys. Laws and institutions ought to move forward to allow the use of data given willingly by their owners (under no duress). A democracy ought to be able to handle this type of process. At the very least, there ought to be a process in place at the European level that allows for this data exchange to happen. It seems evident that non residents phone records are data that are likely to provide the most  useful information quickly (the idea being that they were not exposed for a long time)

- Back in October I was concerned about what we were seeing on the airwaves in terms of rumor propagation, but a week ago, we heard that some Italian Scientists would have to stand trial for manslaughter in the Aquila Quake case. From the Science reporting the story:
According to the Italian daily Corriere della Sera, Gargarella said that the seven defendants had supplied "imprecise, incomplete and contradictory information," in a press conference following a meeting held by the committee 6 days before the quake. In doing so, they "thwarted the activities designed to protect the public," the judge said.

imprecise, incomplete and contradictory information ??? welcome to my world buddy!. Similarly, Bob Park tells us about the recent cell phone controversy

"...CELL PHONES: THE CREDIBILITY OF SCIENCE IS BASED ON OPENNESS.
Let's be open with the public. A Working Group of 31 scientists from 14 countries met at the International Agency for Research on Cancer (IARC) in Lyon, France from May 24–31 to assess the potential carcinogenic hazards from exposure to radiofrequency electromagnetic fields. The Working Group conducted no further study, and gathered no additional evidence. Nevertheless, based on an increased risk for glioma, a usually fatal brain cancer, they voted to classify radiofrequency electromagnetic fields as, "possibly carcinogenic to humans." Let's do a little epidemiology of our own. There are 5 billion cell phones distributed among the 7 billion people on Earth. But, as the New York Times reported this morning, brain cancer rates in the US have been declining for two decades. Does this tell us that cell phones prevent brain cancer? Alas, no. The increase in cell phone use only started one decade ago. It tells us is that epidemiology alone is a lousy guide for making policy. There is far too much "noise" in the data. So far, only photons more energetic than visible light have been shown to create mutant strands of DNA. "Maybe it's a multi-photon process," I'm told. A two-photon process is possible, even a three-photon process, but it would take 1 million microwave photons working in tandem to overcome the work function. So find a mechanism. But please don't inflict more case-control epidemiology on a paranoid public..."
All the cases where technical knowledge is involved, information is initially scant and/or  the science does not exist, are ripe to produces a vacuum in the 24/7 news cycle quickly filled by a whole slew of so-called experts. These experts (most of them have good intentions) have no qualms producing all kinds of scapegoats. For instance, in Germany, incomplete information led to the boycott of cucumbers from Spain leading to huge financial losses there (the E.coli found on cucumbers was eventually found to not be the same strain as the one found in the outbreak). In that theater play called the news, epidemiology as currently performed cannot be an answer. It is not an answer in the cell phone issue as there is no science explaining the process and more importantly statistics doesn't do well in estimating small effects. In order to avoid all these annoying side effects in our hyper-aware and rumor prone societies, shouldn't we push more efforts in evaluating noise and/or applying more machine learning techniques? Small advanced warning signs may be at the heart of figuring out if your outbreak is going to be a major pandemic or if specific types of tremors are going to lead to a major earthquake. Can these problems be identified quickly through some network pattern matching or can we perform better Signal Extraction from Ambient Noise Cross-correlations ? While these examples fit the earthquake problematic, could these techniques be applied to disease outbreaks ? Where do we get more data than just the interviews of sick patients ?

Saturday, June 04, 2011

Kinect Teleconferencing with Real-time 3D Capture and 3D Display

Via KinectHacks.net (I stole their title). Let us think about this for a second, four off the shelf cameras sending structured lighting to get 3-d data are becoming a piece of technology that can disrupt the whole travel industry.


Friday, June 03, 2011

Why Data Mining the Cell Phone Records In Germany is Important in Identifying the HUS Outbreak Source ?

This is a follow-up to Using the Cell Phone Data of Foreigners/Visitors to Find the German E.Coli Source

You will find below two documents from the European Center for Disease Prevention and Control and the Robert Koch Institute (RKI) that point to their level of understanding back on May 26/27th. The Health Ministry of Germany still seems to say that they don't know the source of the outbreak eight days later. The other news are hat the specialists are still asking people what they have eaten when in fact, the two reports below show you that you just need to be in physical contact (hand to hand) with people that have been exposed to it to get sick. In short, getting the cell phone records of sick people might be a much better way to evaluating second hand exposure than asking people if they have eaten raw tomatoes. If the exposure to a large part of the population is due to uncleaned surfaces touched by first exposed people then asking whether they have eaten tomatoes won't help. We now have 12 countries with citizens who have been exposed to this outbreak and so we are beginning to have enough statistics to find out the culprit. 


From a May 27th European Center for Disease Prevention and Control risk assessment:
"...The update provided by Germany on 27 May reports 276 cases of HUS since 25 April. While HUS cases are usually observed in children under 5 years of age, in this outbreak 87% are adults, with a clear predominance of women (68%). Cases in children of school age are also reported. Two people affected by HUS have died. The onset of disease relating to the latest reported case was 25 May. New cases are still being reported.
Laboratory results from samples taken from patients have identified STEC strain of serotype O104:H4 (Stx2-positive, eae-negative). A German study has shown that eae-negative STEC strains generally affect adults more than children. Two strains isolated from patients from Hesse and Bremerhaven were shown to be highly resistant against third  generation cephalosporins (ESBL) and resistant to trimethoprim/sulfonamid and tetracyclines. Most cases are from, or have a history of travel to, northern Germany (mainly Hamburg, Northern Lower Saxony, Schleswig-Holstein). Clusters of cases were reported from Hesse and linked to a catering company that supplies cafeterias. These most likely constitute a satellite outbreak.
The source of the outbreak has not yet been confirmed and intensive investigations are ongoing. German health authorities suspect that contaminated food is the vehicle of the outbreak, based on the epidemiological description (e.g. age and geographical distribution) of the cases. Current investigations are focused on raw vegetables. Preliminary results of a case-control study (with 25 cases and 96 controls) conducted by the Robert Koch Institute (RKI) and the health authorities in Hamburg demonstrate a significant association between disease and the consumption of raw tomatoes, fresh cucumbers and lettuce. Considering that the ongoing outbreak included many cases with a severe course of disease, the RKI and the Federal Institute for Risk Assessment (BfR) recommend people in Germany to abstain from consuming raw tomatoes, fresh cucumbers and leafy salads, especially in the northern part of the country, until further notice. Regular food hygiene rules remain in effect. .."



"...
Preliminary results of the STEC/HUS Case Control StudyPreliminary results of the epidemiological case-control study conducted jointly by the Robert Koch Institute and Hamburg Health Authorities show that the patients affected by the current EHEC outbreak consumed raw tomatoes, cucumbers and lettuce significantly more often compared to the healthy controls. However, whether only one or more of these three vegetables are associated with the outbreak remains unclear.Although the consumption of the described food items could explain the majority of the HUS-cases, other food items cannot be definitely excluded as the source of infection. The study was carried out in Hamburg only; therefore results cannot be generalized to other affected areas in Germany.In total 25 cases with HUS and 96 controls from Hamburg were included in the study since Friday, 20th of May 2011. They were matched according to gender, age group and area of residence. Detailed information concerning consumed food, eating habits and other possible sources of infection was compared between the hospitalized patients and healthy individuals (controls).The outbreak has affected the Northern part of Germany most severely, suggesting that the contaminated food items were mainly distributed there. Nevertheless, as HUS-cases were reported from other parts of Germany as well, contaminated food items could be present in other regions as well.As the outbreak is still ongoing and the public health impact is serious, the RKI and the BfR recommend as a precaution until further notice - in addition to the usual hygienic measures concerning handling of fruits and vegetables – not to eat raw tomatoes, cucumbers and lettuce, especially in the Northern Germany.It remains of vital importance for all persons with diarrhea to follow strict hand hygiene, especially if in contact with small children and immunocompromised individuals. Recommendations for good kitchen hygiene practice, as described in the BfR information sheet (www.bfr.bund.de), remain valid.Date: 26.05.2011.."



Great Thoughts Friday: Using the Cell Phone Data of Foreigners/Visitors to Find the German E.Coli Source

Dirk sent as a comment to the suggestion to use cell phone data to uncover the source (or sources)

Well that approach seems interesting. However, a first issue is that Germany and especially the Germans are peculiar with data privacy and probably there will be an outcry in the media about such an approach. A second issue: How should one interpret the outcome of such an approach. Isn't is probable that the outcome will be something like: "These people visited public restroom frequently" or "have been at Pharmacies or Doctors". In short: How to distinguish cause and effect?

On the first issue: In a democracy, the use of data that has already been collected can always be used for other purposes as long as you have the right filtering tool in effect. I am sure Germany can find ways to set up a privacy commission that oversees the use of this data in times of crisis. Five hundred sick people and  some twenty dead  count as a crisis in my book. 

On the second issue, I recall how John Snow discovered the source of a Cholera source in London: By mapping the location of the sick/dead people by their habitation.



Even he had to do additional thinking after having collected the data (use a diffusion model) to find the epicenter of the disease ( a water handle on Broad street). The way I see I see it, the authorities have no clue. We still don't know if it's in the water system, transportation system, airborne, foodstuff, everything is on the table. Throwing this new layer of information might put additional constraint on the infinite number of solutions they already have (an underdetermined system of some sort).


Of specific interest are the outliers: the foreigners and the Germans not living in Hamburg. Some of them were there for a short time and so are likely the ones whose locations are most interesting. They are probably the ones putting the most constraints on this underdetermined system.


Cassini Movie

I usually pick photos from Cassini to illustrate entries of this blog. Somebody made a movie out of them. Enjoy.


CASSINI MISSION from cabbas on Vimeo.

Thursday, June 02, 2011

Mining the Cell Phone Data to Find the Source of the German Super E-Coli outbreak

A commenter to A solution to finding the E-Coli outbreak source in Germany stated that with 500 cases, mining the cell phone data was not a major undertaking. Let me make the case it is. As far as we understand, we still don't know the nature of the contamination, in effect everything is on the table: water, food, aerial pathogen and it looks like the incubation period is three to eight days. It is not a case of finding out if all these people went to one restaurant or something similar. the issue is figuring out if given all these records, there are other records linking them together. For instance, let us imagine it is a cucumber foodstuff (it looks like it is not), the data mining would figure out all the paths of the sick people and then figure out if all these locations are connected by other cell phone location data ( those of the people selling the sick people the foodstuff). In the end, it may take two or three iterations and additional constraints before having some sorts of the places of interest.  

A solution to finding the E-Coli outbreak source in Germany

The current E-coli outbreak in Germany seems to stun the specialists. Maybe they ought to use other specialists! Here is my proposition, since everybody has a cell phone, including the sick foreigners, get the people at telecom companies to cooperate with the health authorities and provide a travel map of each and everyone (Germans and foreigners) who has become sick (we are talking more than 500 people now) and start some major data mining.

From afar, the problem looks like an instance of randomized group testing.

Printfriendly