Indian Institute of Science Bangalore
etd@IISc Electronic Theses and Dissertations at Indian Institute of ScienceNot a member yet
6204 research outputs found
Sort by
Electrochemical Behavior of Mn-based Oxide Cathode Materials for Alkali-ion Batteries: Study of Cationic and Anionic Redox Reactions
No full textBetter batteries are being developed in response to the growing demand for clean energy in
order to replace conventional fossil fuels with renewable energy for affordable and long-term
energy storage. Lithium-ion batteries have long dominated the markets for electronic goods
and electric vehicles. Alternative monovalent (Na+/K+) metal-ion batteries are being
investigated in light of the diminishing Li sources. The discovery of suitable cathode materials
with effective electrochemical performance is essential for the development of these post-Li-
ion batteries. A variety of oxide materials have been investigated in this effort because of their
high specific capacities, environmental friendliness, and simplicity of synthesis. Oxide
compounds can be found in a variety of structures, including layered structures, spinel
structures, and tunnels with one to three-dimensional diffusion pathways. My research focuses
on examining different insertion compounds for secondary batteries that are based on oxides.
Here, a thorough investigation of various oxide cathodes for metal-ion batteries will be
presented, demonstrating the connection between electrochemical performance and phase
transition. The work is presented in three chapters. Phase pure Na0.44MnO2 compound was
synthesized by using facile solution combustion method taking low-cost nitrates and urea as
precursors. This compound has a 3D tunnel structure and was studied as a host for Li-, Na-,
and K-ion batteries. Following that, phase pure Li0.44MnO2 was synthesized using molten salt
and underlying redox mechanism were explained. The electrochemical activity of layered P2-
oxides
type
[Na0.7Mn0.6Ni0.3Co0.1O2,
Na0.7(Li1/18Mn11/18Ni3/18Fe2/181/18)O2-xNa2MoO4] will be reported. High reversible capacity
over 140 mAh/g, involving both cationic and anionic redox activity, will be demonstrated along
with the effect of cation doping in improving overall performance. Many oxides exhibit
polymorphic phase transition. Li0.44MnO2 was found to undergo tunnel to spinel phase
transition upon annealing with onset point of 463 °C. This phase transition will be depicted
combining in-situ X-ray diffraction, in-situ Raman spectroscopy and in-situ transmission
electron microscopy.MHR
Design and Development of Non-Intrusive Load Monitoring Techniques and Solar Photovoltaic-Thermoelectric Hybrid Energy Conversion Systems
No full textStandalone Solar Photovoltaic (PV) Systems are deployed where access to the conventional Electric Grid is not present. It is necessary to extract most of the available power from the Solar PV modules as the supply is limited. In such cases, the breakdown of energy demand must be monitored in real-time. Energy Disaggregation is employed to understand the components of the loads connected to the system. One of the techniques used for Energy Disaggregation is Non-Intrusive Load Monitoring (NILM). In this approach, only a single, smart energy meter upstream of the demand side is used to estimate the individual constituents of the load, removing the need for multiple sensors to monitor each load. NILM works by training a Machine Learning model through historical data or power signatures of different appliances and deducing individual components in real-time. In the thesis work, the Factorial Hidden Markov Model is applied for NILM wherein the Hidden States of the model, which are the same as the Appliance States, are estimated based on the power signal from the Smart Energy Meter. Training of the Factorial Hidden Markov model requires historical sub-metered data of each appliance which may be challenging to acquire. Significant contributions of this work are to synthetically develop training datasets based on known parameters of appliances using an Energy Demand Model. The appliance datasets are compared with the Indian Dataset for Ambient Water and Energy (iAWE). With the advent of the Internet of Things (IoT) technology, it is now possible to remotely control individual circuits. Another contribution of this work is providing a single platform to monitor and control Appliances using IoT devices. The data regarding the states of these IoT devices is fed back to the NILM algorithm to improve the accuracy and reduce computation times. The other part of the thesis work mainly consists of Solar PV systems with maximum power point tracking. The Optimum value of Voltage and Current needs to be tracked independently of the load and weather conditions. Amongst the Control Strategies, Voltage Control is most prevalent, and there was a need to investigate Current Control as literature is limited. A framework for Current Control Strategies for Boost Converters was developed and experimentally verified. The Hill-Climbing or the Perturb and Observe method was used for implementation, in which momentum based on past perturbations, was introduced which showed improved performance. Further, a domain-independent Bond Graph approach to model hybrid thermoelectric systems was established. A modular Thermoelectric System is designed, which shows potential for Improvement in the Cooling Capacity and Coefficient of Performance of the system. An Active Heating and Cooling controlled chamber with a Standalone Solar PV System including Energy Disaggregation to Monitor the demand is fabricated and installed
Exploring the Fundamental Limits of Information-Theoretically Secure Key Generation and DNA-Based Data Storage
No full textIn this dissertation, we carry out an exploration of the fundamental limits of information-theoretic security in two different settings: multiterminal key agreement and DNA-based data storage. Most of the dissertation focuses on the problem of secret key agreement within the multiterminal source model introduced by Csiszár and Narayan (2004). In the last part of the dissertation, we formulate and characterize a notion of secure storage capacity in the context of DNA-based data storage.
In the multiterminal source model, there is an underlying source that generates independent and identically distributed (i.i.d.) realizations of a random vector. The components of the random vector are finitely-supported random variables distributed according to a joint probability distribution that is specified in the model. Additionally, there is a finite set of users and a wiretapper, each of whom observes the realizations from some subset of the components of the source. The aim of the users is to interactively communicate over a noiseless public channel so that each user finally outputs a common random variable called a secret key, which is required to be secure from the wiretapper. The main object of interest is the wiretap secret key capacity, which is the maximum possible rate of a secret key that can be generated by the users. A substantial part of this dissertation attempts to gain insight into the single-letter characterization of wiretap secret key capacity, which is a problem that has remained largely unsolved.
In the initial part of this dissertation, we explore the connection between secret key agreement and secure omniscience. The problem of secure omniscience is concerned with communication protocols for omniscience that minimize the rate of information leakage to the wiretapper. Our interest is in identifying broad classes of source models for which the wiretap secret key capacity can be achieved through an omniscience protocol that leaks the least possible amount of information to the wiretapper. In such cases, we say that there is a duality between secure omniscience and secret key agreement.
In this dissertation, we show that this duality holds in the case of certain finite linear source (FLS) models, such as two-terminal FLS models and pairwise independent network models on trees with a linear wiretapper. On the other hand, we also give an example of a (non-FLS) source model for which the duality does not hold if we limit ourselves to communication-for-omniscience protocols with at most two (interactive) communications.
Next, we give a characterization of the wiretap secret key capacity under two special situations: one is when the users are not allowed to communicate, and the other is when the communication rate goes to zero asymptotically. We show that both these characterizations have the same single-letter expression, which can be expressed in terms of the maximal common function.
Our focus then shifts to the following question: When can the users generate a positive rate secret key? We give necessary and sufficient conditions for the secret key capacity to be positive, which extend known results on two-terminal sources to the multiterminal setting. For the special case of hypergraphical sources with a linear wiretapper, we derive a simpler equivalent condition for the positivity of secret key capacity in terms of the maximal common function.
The final part of this dissertation is concerned with the study of DNA-based secure data storage. In this problem, a user (Alice) would like to store her data within a pool of (synthetic) DNA molecules so as to be reliably retrieved by an authorized party (Bob) while ensuring that an unauthorized party (Eve) gets almost no information from her (Eve's) observations. We propose a strategy for making DNA-based data storage information-theoretically secure through the use of wiretap channel coding. This motivates us to extend the shuffling-sampling channel model of Shomorony and Heckel (2021) to include a wiretapper. The main contribution is a characterization of the secure storage capacity of our DNA wiretap channel model, which is the maximum rate at which Alice can securely store her data within a pool of DNA molecules
Development and Applications of Portable Raman Spectroscopy Combined with Artificial Intelligence for Biomedicine
No full textCurrently, the global spectroscopic community is investigating the suitability of vibrational spectroscopy methods for point-of-care testing, histopathology, and rapid in-vivo biomedical diagnostics. Although Raman spectroscopy has many benefits, and portable Raman spectroscopy is being used in various fields successfully, currently, it has several difficulties, particularly when it comes to complex samples with low scattering cross-sections such as biological systems.
The main aim of this thesis was to design and develop a portable device using Raman spectroscopy that can be utilized in conjunction with cutting-edge Artificial Intelligence (AI) techniques to obtain and analyse research-grade Raman spectrum from biological samples, which can then be further used for a variety of non-invasive biomedical investigations. Various collection and illumination optical geometries, as well as design issues, were investigated. We proposed a unique three-dimensional image reconstruction (3D tomography) approach for Universal multiple angle Raman spectroscopic (UMARS) data. Several AI/ML approaches and their significance for Raman spectroscopy with data augmentation and database standardization strategies utilized are addressed with the basic implementation of the deep learning models. We demonstrated a novel application of AI combined Raman spectroscopy for DNA-based sub-species-level classification of pathogens. In the second application, the classification of bio-carbon samples derived from pyrolysis was performed with various production conditions using Raman spectroscopy combined with deep learning algorithms such as LeNET, ResNet, and CAE.
An in-house developed portable Raman spectroscopic instrument (“RAIDER”) was used to obtain the Raman spectra from complex samples such as microorganisms. Raman spectral database of highly similar 12 types of bacteria was created, and AI techniques were used for accurate classification. The instrument collected Raman signatures from a variety of bacteria samples with high SNR and compared them to commercially available benchtop instruments. Finally, the potential of an in-house developed portable Raman spectroscopic instrument for in-vivo human skin and blood analysis was explored. Research grade Raman spectra were obtained in-vivo from human skin and blood veins using in-house developed portable instrumentation with high SNR and significantly less exposure than the maximum permissible exposure limit (MPE). Further initial attempts were made to analyse in-vivo melanin content under human skin non-invasively. Variation of the melanin content was evident by biomarkers selected using PCA analysis
Interfacial Engineering of Hierarchical Carbon Fiber Reinforced Epoxy Laminates for Mechanical Property Enhancement and Self-healing Ability
No full textCarbon fiber-reinforced epoxy (CFRE) laminates have become a significant component in aircraft industries over the years due to their superior mechanical and highly tunable properties. However, the interfacial area between the fibers and the matrix continues to pose a significant challenge in debonding and delamination, leading to significant failures in such components. Therefore, since the advent of such laminated structures, researchers have worked on several interfacial modifications to better the mechanical properties and enhance such laminated systems' service life.
In this work, we have successfully fabricated 10 layered hierarchical laminates with engineered interfaces for enhanced matrix adhesion and recovery of interfacial weakly bonded or de-bonded sites that may be causes of subsequent delamination and composite failure. Such architectures could widely be used in aerospace technology, especially in aircraft wings and fuselages. Reduction in fuel and maintenance costs of aircraft structures could be attained through increased structural properties and strength recovery attained by incorporating the advanced laminates presente
Experimental and Numerical Studies on Chemically Active Flame Inhibitors
No full textFire hazards pose an increasingly potent threat to modern societies. Early identification and mitigation of fire hazards are crucial to avoid the loss of human lives and property. Recent research suggests that finely-atomized water spray consisting of droplets with a Sauter Mean Diameter (SMD) of less than 100 µm is a superior fire-suppressant compared to traditional water sprinklers (SMD 0.1 – 1 mm). The addition of chemical inhibitors further improves the effectiveness of water mist as cooling, dilution, and chemical modes of fire suppression are combined. In the present thesis, the effectiveness of chemically active fire suppression agents for methane and LPG flames has been assessed through experiments and numerical modelling. The agents (K/Na-based compounds) are introduced in a counterflow diffusion flame of methane/LPG in the form of aqueous solutions, and their impact on the flame extinction is measured. Initial experiments conducted with pure water mist show a 45% reduction in the extinction strain rate (ESR) at a Y_(H_2 O)=1.5% in a methane flame. It is observed that for both LPG and methane flames, the addition of alkali compounds further improves the inhibition effectiveness of water mist. Four potassium compounds and six sodium compounds have been tested in the present thesis. All potassium compounds show superior effectiveness compared to those of sodium. Among the tested additives, potassium bicarbonate (KHCO3) and potassium acetate (CH3COOK) are established as the most efficient in both methane and LPG flames. In methane flames, the addition of KHCO3 at 2% solute concentration reduces the ESR by 20% as compared to that obtained using a pure water mist. Combinations of multiple compounds are also tested to identify possible synergistic/antagonistic interactions between the agents. Additive interaction is found in the KHCO3 -NaHCO3 mixture, whereas the mixture of KHCO3 – CH3COOK shows antagonistic interaction. To understand these observations, experimental results are compared with one-dimensional simulations using detailed chemical kinetic models. Numerical predictions of the ESR under the influence of water mist are in good agreement with measured data. However, the influence of alkali solutions is only captured qualitatively in the simulations. Numerically, the analysis is extended to other classes of fire suppression agents as well. The ranking among four agents (Fe, K, P, Br-based) is obtained in a methane flame. Additionally, the work closely examines the effect of flame residence time on the inhibitor performance. The importance of regeneration coefficients and radical pool composition in determining the inhibitor effectiveness is established. The detailed chemical mechanism describing the phosphorus-based flame inhibition contains 44 species and 213 reactions, thus making the simulations computationally expensive. The thesis presents two chemical mechanisms, i.e., a skeletal (4 species, 7 reactions) and a global (3 species, 3 reactions) mechanism, which lead to an 82% reduction in computational time with respect to the detailed mechanism. Overall, the thesis has led to an improved understanding of fire suppression under the influence of chemically active flame inhibitors, specifically identifying the most effective potassium-based chemical inhibitors for methane and LPG flames
Efficient Finite Element-Based Approaches for Solving Potential Flow Problems in Fluids
No full textFor many years, fluid flows have been modeled, starting from basic potential flow equations to full Navier-Stokes equations. The complexity of the flow increases as viscous effects, boundary layer, and flow separation are included in the fluid flow problem. However, at the preliminary design level, a simple technique to solve fluid flow problems becomes necessary for the quick assessment of 2-D aerodynamic concepts. Conventional panel methods have been popular in solving potential flow problems due to their ease of implementation for simple geometries such as circular bodies, airfoils, and 3-D applications such as wings. Nevertheless, the method becomes computationally expensive when a large number of boundary elements are required or for time-dependent problems. Moreover, due to established techniques such as panel methods, other methods go unexplored, or a smaller extent of literature is available.
The present research aims to develop a Finite Element Method (FEM) for potential flows over a range of bluff bodies like cylinders to streamlined profiles such as airfoils. In contrast to conventional panel methods, Laplace’s equation describing the potential flow was solved here for the velocity potential function using the Galerkin method. A brief discussion on edge singularities in potential flows has also been presented using a half-cylinder case study.
A novel method for implementing Kutta condition over airfoils to have a lifting flow has been investigated. Compared with other techniques such as finite difference and volume methods, the present methodology has proven to be computationally faster for airfoils with both finite angle and cusped trailing edges. The results have demonstrated excellent accuracy compared to analytical and panel methods.
The present novel Kutta condition method has been extended to quasi-unsteady flows to show its ease of adaptability for various steady and time-dependent conditions. The process of vortex shedding in the wake of an airfoil and building up of forces was studied. A case study of a sudden step change in the angle of attack was considered for quasi-unsteady flow over an airfoil, and the results were in good accordance with the panel methods.
Lastly, the application of the present FEM program was presented for a case of converting 2-D airfoil section data into 3-D wing data. 3-D wings with elliptic, rectangular, and trapezoidal planforms with tapering, sweep angle, and twist were considered. Mathematical formulas were derived from lifting-line theory, and an integration approach was used to calculate the aerodynamic coefficients. The results obtained are in good agreement with the experiments. Predicting data for 3-D wings from 2-D section airfoil using the present FEM program appears to be a very viable and cost-efficient method. Finally, the 2-D longitudinal profile of a sedan-type vehicle was considered to check the program's capability for evaluating geometries other than an airfoil. The present potential flow results for a sedan car and a modified sedan car were compared with the viscous model in ANSYS Fluent. It was observed that streamlining the sectional profile of the sedan would predict results closer to the real viscous flow due to minor flow separation
An Experimental Investigation of Transitional and Turbulent Channel Flow
No full textThis thesis is a comprehensive experimental investigation of transitional and turbulent channel
flow in the Reynolds number range of Reτ = 55 − 1559. Towards this objective, a new
channel flow facility was designed and built, with a very high area contraction ratio of 108.
This is achieved by building a channel of cross section 600 mm × 50 mm, length 7320 mm
and connecting it to the downstream section of a blower wind tunnel. Two-dimensional (x-y
plane along the mid-span of the channel) velocity field is measured using particle image velocimetry,
hot-wire anemometry and Pitot tube. The contractions are carefully designed with
optimal parameters to have minimal non-uniformity at the exit. This ultra high contraction ratio
causes large reduction in the disturbance levels leading to delay in the onset of transition (at
Rem = 2050, rather than the usual value of around 1500) and protraction of the extent of the
transitional regime by around 4 times (ΔRem = 3150, as opposed to the usual value of around
800). Here Rem is the bulk Reynolds number.
A new scaling law for velocity in the transitional region has been obtained based on the
present measurements. The mean velocity in the transitional region is scaled by the centerline
velocity, and displays a log law given by u/Uc = 0.13ln(y/h) + D1 with a ‘universal’ slope
of 0.13. For the relatively quiet channel of the present study, this holds over a range of about
0.3 ≤ y/h ≤ 0.6. The results are compared with experimental and DNS data from literature
for the configurations channel, pipe and boundary layer to confirm the universality of the
slope, where they are valid over a smaller range. Using this, a relation for skin friction in the
laminar-turbulent transitional flow is derived by a methodology similar to that of Prandtl for
fully turbulent flow. From this, an expression for pressure drop in a channel (or pipe) as a function
of bulk velocity is obtained, consistent with the well known Darcy-Weisbach relation. For
the present experiments, pressure drop is given by ΔP ∝ un
m, where n = 1.0, 2.5, 1.75 respectively
for laminar, transitional and turbulent zones. While the results for laminar and turbulent
regimes are already known, the one for the transitional regime is a new result.
The scaling of mean velocity in the turbulent region, given by the long known and celebrated
log law (Millikan (1938)), is an asymptotic expectation. A stringent test for the validity
of the log law for finite Reynolds numbers is the constancy of the so-called diagnostic function
in the inertial sublayer. However, for turbulent channel flow, the diagnostic function does not
become constant till about Reτ = 5200 (?? and hence the standard log law does not accurately
predict the mean velocity for Reτ < 5200. A modified version of the log law is derived from the
mean flow momentum equation, which accounts for low Reτ and viscous effects. For closure
Townsend (1980) is followed, wherein the turbulent kinetic energy equation is simplified to obtain
a mixing-length-like relation between Reynolds shear stress and the mean velocity gradient.
The resulting expression for mean velocity is seen to be consistent with the experimental and
direct numerical simulation data in the inertial sublayer compared to the standard log law. This
is further extended using a composite mixing length estimate for the outer layer along with the
inertial sublayer and the agreement of the predicted mean velocity with experimental and direct
numerical simulation data is excellent at high Reτ in the outer region. While both the modified
and extended log law expressions work reasonably well in predicting the mean velocity from
present experiments and DNS of Lee and Moser (2015), the prediction of diagnostic function
was not satisfactory. However, when the variation of the structure parameter was accounted for,
the prediction of diagnostic function was very good. Overall this vindicates a mixing length
model as derived from the turbulent energy equation as proposed by Townsend (1980). Further,
instantaneous uniform momentum zones (UMZs) are examined and found to exist in a turbulent
channel flow at moderately high Reτ .
Next, the scaling of streamwise turbulence intensity (Townsend (1980)) is examined. This
scaling which yields a log law for turbulence intensity, seems to occur only at fairly high Reτ
in the literature. The notion of active and inactive motions was introduced by Townsend (1961)
(see also Bradshaw (1967)). It is proposed here that the non-occurrence of the log-law scaling
for turbulence intensity at lower Reynolds numbers such as those of the present experiments
are perhaps due to the obfuscatory effect of ‘inactive motions’. By using the so-called episodic
description of wall turbulence (Narasimha et al. (2007)), the flow is split into active and inactive
parts. The universal or active part of turbulence intensities so separated, display a universal
logarithmic slope of -1.26 even at moderate Reynolds numbers while the log-law intercept in
non-universal. This is also a vindication of the methodology to separate active and inactive
parts followed herein. Conceptually, a connection between episodic descriptions and the active/
inactive description is also established.
Next, the distribution of mean and fluctuating spanwise vorticities in the transitional and
moderately turbulent regimes are considered. Dimensional mean vorticity profiles plotted for
both transitional and turbulent regimes show that mean vorticity increases with Reynolds number
close to the wall much more than away from the wall. This is well quantified by an integral
quantity, akin to displacement thickness for a boundary layer, called centroid of mean vorticity.
This centroid reduces monotonically with Reynolds number showing progressive migration of
mean vorticity towards the wall. Likewise for fluctuating vorticity also, a centroid is defined in a
similar manner. The centroid of fluctuating vorticity was also found to decrease monotonically
with Reynolds number, in both transitional and turbulent regimes, showing increased concentration
of fluctuating vorticity towards the wall as the Reynolds number is increased. Probability
density function (PDF) of fluctuating spanwise vorticity were seen to be particularly peaky in
the core region. Combined with a vanishingly small mean vorticity, a peaky PDF would signify
a highly intermittent behaviour. However, we are not able to directly verify the intermittent vortical
behaviour from the present study as the vorticity measurement is not time-resolved. Near
the wall though, the PDF is less peaky and the mean is also nonzero. Taken together, this indicates,
in outer co-ordinates, the vorticity concentration shifts towards the wall with Reynolds
number. The (dimensional) vorticity fluctuation increases in the outer region also with Reynolds
number, but at a much slower rate compared to the near-wall regions. We anticipate that this
tendency is likely to accentuate at very high and ultra high turbulent Reynolds numbers outside
the range of present studies. Further, two-point correlation with respect to the wall is measured
using hotwire anemometry. Results show that the average inclination angle of the correlated
structures decrease with Reynolds number, consistent with the corresponding inward vorticity
migration.
The next question that is addressed is that of interaction of inner and outer regions of a
channel. The footprints of this activity manifest as a very large wavelength activity or very large
scale motion (VLSM) in the power spectra of streamwise velocity fluctuation. We propose a
scaling to relate the VLSM wavelengths (λ close to the centreline of the channel, with the time
scale (T) of the corresponding low frequency activity displayed by the wall-normal velocity at
the centerline. Further, the vertical velocity at the centerline has been split using kinematics into
three terms. The first term (d/dx(Ucδ∗)) is instantaneous streamwise derivative of mass defect
up to the centreline. The second term (hdUc/dx) is acceleration/deceleration of the freestream,
is possibly due to the instantaneous response from the other side of the channel. The third
term (R h0∂w∂z dy) is due to instantaneous dilation in the spanwise direction and the fourth term
(vw) is due to wall transpiration (zero in the present case). The time series of the terms seems
to signify a quasi-periodic see-saw like acceleration/deceleration of the streamwise centerline
velocity due to the interaction between both the sides of the channel
Improved Algorithms for Variants of Bin Packing and Knapsack.
No full textWe study variants of two classical optimization problems: Bin Packing and Knapsack. Both bin packing and knapsack fall under the regime of "Packing and Covering Problems". In bin packing, we are given a set of input items, each with an associated size, and the objective is to pack these into the minimum number of unit capacity bins. On the other hand, in the knapsack problem, each item has an additional profit associated with it. The objective is to find a maximum profitable subset that can be packed into a unit capacity knapsack. Both bin packing and knapsack find numerous applications; however, both turn out to be NP-Hard. Hence, it is natural to seek approximation algorithms for these problems. Lawler settled the knapsack problem by giving an FPTAS, whereas the progressive works of de la Vega and Lueker, Karmarkar and Karp, and Rothvoss have given improved approximation schemes for the bin packing problem. However, many variants of these problems (e.g., multidimensional, geometric, stochastic) also find wide applicability, but haven't been settled. We make progress on this front by providing new and improved algorithms for several such variants.
First, we study bin packing under the i.i.d. model, where item sizes are sampled independently and identically from a distribution in (0,1]. Both the distribution and the total number of items are unknown. The items arrive one by one, and their sizes are revealed upon their arrival, and they must be packed immediately and irrevocably in bins of unit size. We provide a simple meta-algorithm that takes an offline \alpha-asymptotic approximation algorithm and provides a polynomial-time (\alpha+\epsilon)-competitive algorithm for online bin packing under the i.i.d. model, where \epsilon>0 is a small constant. Using the AFPTAS for offline bin packing, we thus provide a linear time (1+\epsilon)-competitive algorithm for online bin packing under the i.i.d. model, thus settling the problem.
Then we study a well-known geometric generalization of the knapsack problem, the 3-D Knapsack problem. In this problem, the items are cuboids in three dimensions, and the knapsack is a unit cube. The objective is to pack a maximum profitable subset of the input set in a non-overlapping, axis-parallel manner inside the knapsack. Depending on whether rotations around axes (by ninety degrees) are allowed or not, we obtain two variants. [DHJTT'07] gave a (7+\epsilon) (resp. (5+\epsilon)) approximation algorithm for the 3D Knapsack problem without rotations (resp. with rotations). Despite the importance of the problem, there has been no improvement in the ratios for fifteen years. First, we give alternate algorithms that achieve the same approximation ratios (7+\epsilon, 5+\epsilon). These algorithms and their analyses are far simpler. Then, for the case when rotations are allowed, we give an improved (31/7+\epsilon) approximation algorithm in the general setting, and a (3+\epsilon) approximation algorithm in the important special case where each item has a profit equal to its volume.
We also introduce and study a generalization of the knapsack problem with geometric and vector constraints. The input is a set of rectangular items, each with an associated profit and d nonnegative weights (dD vector), and a square knapsack. The goal is to find a non-overlapping, axis-parallel packing of a subset of items into the given knapsack such that the vector constraints are not violated, i.e., the sum of weights of all the packed items in any of the d dimensions does not exceed one. Two variants are defined: rotations allowed by 90 degrees and rotations not allowed. We give (2+\epsilon)-approximation algorithms for both variants.
Finally, we consider the problem of packing d-D hypercubes into a knapsack defined by the region [0,1]^d. Each hypercube has an associated profit, and the goal is to find a maximum profitable non-overlapping, axis-parallel packing. We consider two special cases of this problem: (i) cardinality case, where each item has unit profit, (ii) bounded profit-volume ratio case, where the profit-to-volume ratio of each item lies in the range [1,r] for some fixed constant r. We give near-optimal algorithms for both cases
Improved air-tissue boundary segmentation in real-time magnetic resonance imaging videos using speech articulator specific error criterion
No full textReal-time Magnetic Resonance Imaging (rtMRI) is a tool used exhaustively in speech science and linguistics to understand the dynamics of the speech production process across languages and health conditions. rtMRI has two advantages over other methods which capture articulatory movement, like X-ray, Ultrasound and Electromagnetic articulography - it is non invasive, and it captures a complete view of the vocal tract including pharyngeal structures. The rtMRI video provides spatio-temporal information of speech articulatory movements, which helps in modeling speech production. For this purpose, a common step is to obtain the air-tissue boundary (ATB) segmentation in all frames of the rtMRI video. The accurate estimation of ATBs of the upper airway of the vocal tract is essential for many speech processing applications like speaker verification, text-to-speech synthesis, visual augmentation for synthesized articulatory videos, and analysis
of vocal tract movement. Thus, it is necessary to have an accurate air-tissue boundary segmentation in every frame of the rtMRI videos.
The best performance in ATB segmentation of rtMRI videos in speech production, in unseen subject conditions, is known to be achieved by a 3-dimensional convolutional neural network (3D-CNN) model. In seen subject conditions, both 3D-CNN and 2-dimensional deep convolutional encoder-decoder network (SegNet) show similar performance. However, the evaluation of these models, as well as other ATB segmentation techniques reported in literature, has been done using Dynamic Time Warping (DTW) distance between the entire original and predicted boundaries or contours. Such an evaluation measure may not capture local errors in the predicted contour. Careful analysis of predicted contours reveals
errors in regions like the velum part and tongue base section, which are not captured in a global evaluation metric like DTW distance. In this thesis, such errors are automatically detected and a novel correction scheme is proposed for them. Two new evaluation metrics are also proposed for ATB segmentation, separately for each contour, to explicitly capture errors in these contours.
Moreover, the state-of-the-art models use overall binary cross entropy as the loss function during model training. However, such a global loss function does not give enough emphasis on regions which are more prone to errors. In this thesis, together with global loss, the use of regional loss functions has been explored, which focus on areas of the contours which have been analyzed as error prone in the analysis. Two different losses are considered in the regions around velum and
tongue base - binary cross entropy (BCE) loss and dice loss. It is observed that dice-loss based models perform better than their BCE loss based counterparts