Playing Poseidon: A Lattice Boltzmann Approach to Simulating Generalised Newtonian Fluids

Nitish Tripathi (homepage)

Abstract

Imitating the behaviour and characteristics of fluids with the help of a computer is called fluid simulation. Real world fluids are fickle. They are subtle and gentle at times; at times they are ravenous and tumultuous. Needless to say, complex equations are behind even the tiniest of ripple, so much so that often fluid mechanics has been described as ”the physicists nightmare”. Yet there are few, if any, substances which are so beautiful and graceful in motion to observe. To an ardent student of hydrodynamics, everything in the discernible world is fluid. Solids may just be classified as fluids which flow extremely slowly! Given time, every substance has the tendency to flow under the influence of an external force.

The history of fluid simulations, thus, rightly, begins with the formulation of the Navier Stokes’ equations. These were a set of partial differential equations originally developed in the 1840s on the basis of conservation laws and first order approximations. What followed was the Conventional study of fluid flows for more than a century. Arriving at computational models to solve fluid equations has been a subject of research since the early 1950s. Finding solutions to the partial differentials of Navier Stokes’ equations using discrete algorithms was area of focus. Many modern day techniques, of which some will be skimmed through in the succeeding chapters, came up during that time. Staggered marker-and-cell (MAC grid structure), Particle in Cell (PIC method) etc. are two of those.

However, most of the models and techniques developed by the CFD community then was complex and unscalable for visual effects oriented computer graphics. In the succeeding years, fluid effects was generated using non-physics based methods, such as using hand drawn animation (key frame animation) or displacement mapping.

The development of fluid simulations has traditionally been in two concurrent streams, viz., Eulerian and Lagrangian Simulations. Eulerian Method involves modelling the fluid as a collection of scalar fields (density, pressure etc.) and vector fields (velocity etc.). Each field is calculated using Navier Stokes’ equations and fluid is visualised as crossing the volume at fixed grid points, where the value of each field is known. Lagrangian simulations on the other hand take a more intuitive approach. They treat fluid particles as carriers of the field values in accordance with the Navier Stokes’ equations. The dependence of both the methods on Navier Stokes’ makes them essentially top down simulations methods - these methods look at what the perceptible fluid properties are without concerning themselves about the kind of particular interactions which give rise to the said properties.

Lattice Boltzmann Method developed around the same time but did not come into widespread usage until much later. Unlike the conventional methods, it is a statistical method based on Kinetic Theory. It treats fluids as a collection of logical mesoscopic particles. These are constrained to move in a discrete set of directions across a cartesian grid. They follow continuous alternating iterations of colliding at each grid centre and redistribution around it, and, progressing to the neighbouring centre. It was shown that for a particular kind of collisions these particular interactions give rise to Navier Stokes’ properties at the macro level. However, we can tweak certain parameters during the development so that quantities, taken to essentially be constants in the final Navier Stokes’ equations, can be varied to simulate fluids outside their scope. As we will see in the succeeding chapters, such fluids are in abundance around us and are called non-Newtonian fluids. The Navier Stokes’ equation, as will also be seen in succeeding chapters, are essentially Newton’s second law of motion. It is therefore unfit to deal with fluids which are non-Newtonian in nature and requires regular tweaking to model them.

In this work, we combine physical models of non-Newtonian fluids with Lattice Boltzmann Method. We give the CPU implementation, showing how easy it is to understand and code. We show how the method, inspite of its ease of implementation, doesn’t compromise on physical realism or accuracy. We also give a model for GPU implementation for increased efficiency and interactive frame rates.

Related Publications

• Tripathi, N. and Narayanan, P.J. Generalized newtonian fluid simulations. 2013 Fourth National Conference on Computer Vision, Pattern Recognition, Image Processing and Graphics (NCVPRIPG-2013). Jodhpur, India. [PDF]
• Jain, Somay and Tripathi, Nitish and Narayanan, P. J. Interactive Simulation of Generalised Newtonian Fluids Using GPUs. Proceedings of the 2014 Indian Conference on Computer Vision Graphics and Image Processing (ICVGIP-2014). Bangalore, India. [PDF]

Downloads

Diversity in Image Retrieval using Randomization and Learned Metrics

P Vidyadhar Rao (homepage)

Abstract

Providing useful information to user requested queries is the most investigated problem in the multi-media retrieval community. The problem of information retrieval usually has many possible solutions, due to uncertainties in the user's information need and ambiguities in query specification. Some mechanism is required to evaluate the options and select a solution. This is quite a challenging task. In the recent years, the focus is gradually shifting towards relevance and diversity of retrieved information, which together improve the usefulness of retrieval system as perceived by users. Intuitively it is desirable to design a retrieval system with three requirements: a) Accurate retrieval i.e., the method should have high precision, b) Diverse retrieval, i.e., the obtained results should be diverse, c) Efficient retrieval, i.e., response time should be small. While considerable effort has been expended to develop algorithms which incorporate both relevance and diversity in the retrieval process, relatively less attention has been given to the problem of finding efficient diverse retrieval algorithms.

The main contribution of this thesis lies in developing efficient algorithms for the diverse retrieval problem. We show that the diverse retrieval problem can be mathematically defined as an integer convex optimization problem, and hence finding the optimal solution is NP-Hard. The existing approximate and greedy algorithms that try to find solution to this problem suffer from two drawbacks: a) Running time of the algorithms is very high as it is required to recover several exact nearest neighbors. b) Computations may require an unreasonably large amount of memory overhead for large datasets. In this work, we propose a simple approach to overcome all the above simultaneously based on two ideas: 1) Randomization and 2) Learned Metrics.

In the first case, the method is based on locality sensitive hashing and tries to address all of the above requirements simultaneously. We show that the effectiveness of our method depends on randomization in the design of the hash functions. Further, we derive a theoretically sound result to support the intuitiveness and reliability of using hash functions (via randomization) in the retrieval process to improve diversity. We modify the standard hash functions to take into account the distribution of the data for better performance. We also formulate the diverse multi-label prediction(of images and web pages) in this setting and demonstrate the scalability and diversity in the solution. We demonstrate effectiveness of our approach in three tasks: Image Category Retrieval, Multi-label Classification and Image Tagging. Our findings show that the proposed hash functions in combination with the existing diversity-based methods significantly outperforms standard methods without using hash functions. Our method allows to achieve a trade-off between accuracy and diversity using easy to tune parameters. We examine evaluation measures for diversity in several retrieval scenarios and introduce a new notion to simultaneously evaluate a method's performance for both the precision and diversity measures. Our proposal does not harm, but instead increases the reliability of the measures in terms of accuracy and diversity while ensuring $100x$-speed-up over the existing diverse retrieval approaches.

In the second case, the method is based on learning distance metrics. We show that effectiveness of our method depends on the learned distance metrics that suits the user's interest. In the case of instance based image retrieval methods, relevance and diversity are relative to users viewpoint of the camera, time of day, and camera zoom. We argue that the low-level image features fail to capture diversity with respect to high-level human semantics. We, therefore, use the high-level semantic information to learn metrics and re-fashion the visual feature space to appreciate diversity better in the retrieval. Our experiments confirm that our proposal is the best strategy from a learning perspective, when compared to original feature space, that the learned metrics provide better diversity in the retrieval.

In conclusion, in this thesis we discussed two fundamental ideas for retrieving diverse set of results. From the algorithmic and statistical perspective, the proposed method intuitively uses "randomness as resource" to improve diversity in retrieval while ensuring sub-linear retrieval time. From the visual perspectives, the proposed method utilizes user level semantics to "learn metrics" for improving diversity in instance based image retrieval. We believe that the ideas presented in this thesis are not limited to image retrieval and therefore, its applicability to different definitions of diversity (visual, temporal, spatial, and topical aspects), knowledge source combination (image and text), interactive retrieval systems (relevance feedback), and so forth are possible.

Related Publications

• Vidyadhar Rao, Ajitesh Gupta, Visesh Chari, C. V. Jawahar - Learning Metrics for Diversity in Instance Retrieval Proceedings of the 5th National Confernece on Computer Vision, Pattern Recognition, Image Processing and Graphics, 16-19 Dec 2015, Patna, India. [PDF]
  

• Vidyadhar Rao and C V Jawahar - Semi-Supervised Clustering by Selecting Informative Constraints Proceedings of 5th International Conference on Pattern Recognition and Machines Intelligence (PReMI), 10-14 Dec. 2013, Kolkata, India. [PDF]

Downloads

Time Frequency Analysis for Motion Magnification and Detection

Sushma M. (homepage)

Motion can be defined as change in position of an object of interest with respect to time. This thesis explores the methods of analyzing motion using time frequency analysis. In this thesis, we address two problems: (i) Small Motion Magnification in Videos and (ii) Motion Detection in Perfusion Weighted Imaging (PWI).

Human eye and its brain interface can visualize or detect the motion within a certain range of spatial and temporal frequencies. But in most of the cases, it might be possible that frequencies which are below this range also can have useful information. We can simplify this by saying that there can be small motions which are not visible to the naked eye. Even though these small motions are difficult to detect, they may contain useful information. In first part of thesis, we present a semi-automated method to magnify small motions in videos. This method amplifies invisible or hidden motions in videos. To achieve motion magnification, we process the spatial and temporal information obtained from the video itself. Advantage of this work is that it is application independent. Proposed technique estimates required parameters to get desirable results. We demonstrate performance on a few videos. Motion magnification performance is equivalent to existing manual methods.

In second part of thesis, we present a novel automated method to detect motion in perfusion weighted images (PWI), which is a type of magnetic resonance imaging (MRI). In PWI, blood perfusion is measured by injecting an exogenous tracer called bolus into the blood flow of a patient and then tracking it in the brain. PWI requires a long data acquisition time to form a time series of volumes. Hence, motion occurs due to patient's unavoidable movements during a scan, which in turn results into motion corrupted data. There is a necessity of detection of these motion artifacts on captured data for correct disease diagnosis. In PWI, intensity profile gets disturbed due to occurrence of motion and/or bolus passage through the blood vessels. In this work, we propose an efficient time-frequency analysis based motion detection method. We show that proposed method is computationally inexpensive and fast. This method is evaluated on a DSC-MRI sequence with simulated motion of different degrees. We show that our approach detects motion in a few seconds.

Related Publications

• Sushma M., Anubha Gupta and Jayanthi Sivaswamy - Time-Frequency Analysis based Motion Detection in Perfusion Weighted MRI Proceedings of the IEEE National Conference on Computer Vision, Pattern Recognition, Image Processing and Graphics (NCVPRIPG), 18-21 Dec. 2013, Jodhpur, India. [PDF]

• Sushma M., Anubha Gupta and Jayanthi Sivaswamy - Semi-Automated Magnification of Small Motions in Videos Proceedings of 5th International Conference on Pattern Recognition and Machines Intelligence (PReMI), 10-14 Dec. 2013, Kolkata, India. [PDF]

Downloads

Synthesizing Classifiers for Novel Settings

Viresh Ranjan (homepage)

Computer vision systems have been developed which perform well at recognizing and retrieving natural images as well as document images. However,these systems might not work well under certain scenarios, for instance, when the distribution of the training and the test data do not match. For example, an ocr system may not work on those target fonts which are very different from the fonts used while training. Moreover, such systems might not be able to tackle previously unseen categories. These scenarios limit the real world applications of Computer vision systems to some extent. In this thesis, we tackle these problems by designing classiffers that could work in novel scenarios. We design algorithms for retrieving from document images, as well as recognizing objects and digits in novel settings.

For the document image retrieval task, we consider two different problems. In the first scenario, we tackle the issue of novel query words in a classifier based retrieval system. We present a one-shot learning strategy for the learning of discriminative classifiers given a novel query word. This strategy utilizes the classifiers learned at the training time in order to obtain the classifier corresponding to the underlying query class. This extends the classifier based retrieval paradigm to an unlimited number of classes(words)present in a language. We validate our method on multiple data sets, and compare it with popular alternatives like ocr and word spotting. In the second scenario, we tackle the problem of mismatch between the source and the target style(font). We tackle this problem by style(font)-content(word label)factorization strategy. Based on the style-content factorization, we present a semi-supervised style transfer strategy to transfer word images in the source font to the target font. We also present a nonlinear style content factorization for obtaining style independent representation of word images. We validate both these strategies on scanned document collections as well as multifont synthetic data sets. We show mean average precision gains of upto 0.30 over the baseline using our nonlinear factorization strategy.

For the recognition task, we consider the data set mismatch scenario between the source and the target data. In such a scenario, the classifiers trained on the source data might perform poorly on the target data. We tackle two different tasks in this scenario, i.e. digits recognition and object recognition. The two domains we consider for the digits recognition task are handwritten and printed digits. To tackle the digits recognition task,we present a subspace alignment based strategy. In this approach, labeled source domain data and unlabeled target domain data is used to learn transformations for the two domain which reduces the mismatch between the two domains. A source domain classifier learned after applying the transformations would work well even on the target domain data. We consider the simple nearest neighbor based classifier for validating this claim. For the object recognition task, we present a sparse representation based strategy. A dictionary learned from the source data might not be suitable for sparsely representing target domain data and vice-versa. Hence, we present a partially shared dictionary learning strategy which results in dictionaries which are suitable for representing the source as well as the target domains. We show our results on popular benchmark data sets and show improvement over the state of art approaches. (more...)

Related Publications

• Viresh Ranjan, Gaurav Harit, C. V. Jawahar - Document Retrieval with Unlimited Vocabulary Proceedings of the IEEE Winter Conferenc on Applications of Computer Vision, 06-09 Jan 2015, Waikoloa Beach, USA. [PDF]
  

• Viresh Ranjan, Gaurav Harit, C. V. Jawahar - Domain Adaptation by Aligning Locality Preserving Subspaces Proceedings of the Eighth International Conference on Advances in Pattern Recognition (ICPR),04-07 Jan 2015, Kolkata, India. [PDF]
  

• Viresh Ranjan, Gaurav Harit, C.V. Jawahar - Learning Partially Shared Dictionaries for Domain Adaptation Proceedings of the 12th Asian Conference on Computer Vision,01-05 Nov 2014, Singapore. [PDF]
  

• Viresh Ranjan, Gaurav Harit, C. V. Jawahar - Enhancing Word Image Retrieval in Presence of Font Variations, 22nd International Conference on Pattern Recognition(ICPR) , 2014(Oral), [PDF]

Downloads