KEYWORDS: CMYK color model, Data modeling, Data conversion, Printing, Image compression, Data centers, Space operations, Mathematical modeling, RGB color model, Digital image processing
A new technique is described for color conversions of JPEG images. For each input block of each
component, the conversion for the 63 AC coefficients is processed in the transform domain instead of the
spatial domain. Only the DC coefficients for each input block of the color components are transformed to
the spatial domain and then processed through the traditional lookup table to create color-converted output
DC coefficients for each block. Given each converted DC value for each block, the remaining 63 AC
coefficients are then converted directly in the transform domain via scaling functions that are accessed via a
table as a function of only the DC term. For n-dimensional color space to m-dimensional color space
conversion, n component blocks create m component blocks. An IDCT can then be applied to the m
component blocks to create spatial domain data or these output blocks can be quantized and entropy
encoded to create JPEG compressed data in the m-dimensional color space.
Converting images between color spaces is a computationally very demanding task. The conversion is based on lookup tables that have an output colorspace value defined for each node in a mesh that covers the input space. If the input color value to be converted is not a mesh node, the output is computed by interpolating values in the surrounding mesh nodes. For a three dimensional input space, such as the RGB, tetrahedral and trilinear interpolations are used. If the input space is four dimensional, quadrilinear interpolation is used. This paper discusses how to reduce the complexity of lookup
table implementation by exploiting the relationships between input and output color space components and using moderate lookup table expansion to achieve significant speed advantage. For example, a CMYK to K conversion, commonly implemented using quadrilinear interpolation on a 9x9x9x9 mesh can be reduced to bilinear interpolation
assuming the mesh can grow from 6561 nodes to 684288 nodes.
Large classes of data association problems in multiple hypothesis tracking applications, including sensor fusion, can be formulated as multidimensional assignment problems. Lagrangian relaxation methods have been shown to solve these problems to the noise level in the problem in real-time, especially for dense scenarios and for multiple scans of data from multiple sensors. This work presents a new class of algorithms that circumvent the difficulties of similar previous algorithms. The computational complexity of the new algorithms is shown via some numerical examples to be linear in the number of arcs.
The ever-increasing demand in surveillance is to produce highly accurate target and track identification and estimation in real-time, even for dense target scenarios and in regions of high track contention. The use of multiple sensor, through more varied information, has the potential to greatly enhance target identification and state estimation. For multitarget tracking, the processing of multiple scans all at once yields high track identification. However, to achieve this accurate state estimation and track identification, one must solve an NP-hard data association problem of partitioning observations into tracks and false alarms in real-time. The primary objective in this work is to formulate a general class of these data association problems as a multidimensional assignment problem to which new, fast, near-optimal, Lagrangian relaxation based algorithms are applicable. The dimension of the formulated assignment problem corresponds to the number of data sets, and the constraints define a feasible partition of the data sets. The linear objective function is developed from Bayesian estimation and is the negative log likelihood function, so that the optimal solution yields the maximum likelihood estimate. After formulating this general class of problems, the equivalence between solving data association problems by these multidimensional assignment problems and by the currently most popular method of multiple hypothesis tracking is established. Track initiation and track maintenance using an N-scan sliding window are then used as illustrations.
The central problem in multitarget-multisensor tracking is the data association problem of partitioning the observations into tracks and false alarms so that an accurate estimate of the true tracks can be recovered. Many previous and current methodologies are based on single scan processing, which is real-time, but often leads to a large number of partial and incorrect assignments, and thus incorrect track identification. The fundamental difficulty is that data association decisions once made are irrevocable. Deferred logic methods such as multiple hypothesis tracking allow correction of these misassociations and are thus considered to be the method for tracking a large number of targets. The corresponding data association problems are however NP-hard and must be solved in real-time. Such algorithms have been developed in earlier work of the authors and the intent of this work is to demonstrate the efficiency and robustness on a class of tracking problems.
The central problem in multitarget-multisensor tracking is the data association problem of partitioning the observations into tracks and false alarms so that an accurate estimate of the true tracks can be recovered. Many previous and current methodologies are based on single scan processing, which is real-time, but often leads to a large number of partial and incorrect assignments, and thus incorrect track identification. The fundamental difficulty is that data association decisions once made are irrevocable. Deferred logic methods such as multiple hypothesis tracking allow correction of these misassociations and are thus considered to be the method for tracking a large number of targets. The corresponding data association problems are however NP-hard and must be solved in real-time. The current work develops a class of algorithms that produce near-optimal solutions in real-time and are potentially orders of magnitude faster than existing methods.
KEYWORDS: Signal processing, Data processing, Sensors, Detection and tracking algorithms, System identification, Target detection, Gadolinium, Optimization (mathematics), Algorithm development, Dynamical systems
The central problem in multitarget-multisensor tracking is the data association problem of partitioning the observations into tracks and false alarms so that an accurate estimate of the true tracks can be recovered. Many previous and current methodologies are based on single scan processing, which is real-time, but often leads to a large number of partial and incorrect assignments, and thus incorrect track identification. The fundamental difficulty with this approach is that there is simply not enough information in single scan processing to properly partition the observations into tracks and false alarms. In this work we formulate the problem of data association for track initiation and extension using multiscan windows in order to obtain superior track identification. A model problem is investigated to show the effect of window size, probability of detection, probability of false alarms, and measurement error on solution quality and timings.
KEYWORDS: Detection and tracking algorithms, Algorithm development, Signal processing, Data processing, Digital filtering, Data modeling, Target detection, Electronic filtering, Optimization (mathematics), Lithium
A fundamental problem in multi-target tracking is the data association problem of partitioning the observations into tracks and false alarms so that an accurate estimate of the true tracks can be recovered. Here, this problem is formulated as a multi-dimensional assignment problem using gating techniques to introduce sparsity into the problem, filtering techniques to generate tracks which are then used to score each assignment of a collection of observations to its corresponding filtered track. Problem complexity is further reduced by decomposing the problem into disjoint components using graph theoretic methods. A recursive Lagrangean relaxation algorithm is then developed to obtain high quality suboptimal solutions in real-time. The algorithms are, however, applicable to a large class of sparse multi-dimensional assignment problems arising in general multi-target and multi-sensor tracking. Results of extensive numerical testing are presented for a case study to demonstrate the speed, robustness, and exceptional quality of the solutions.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.