Image analysis – Image transformation or preprocessing
Reexamination Certificate
2006-07-25
2010-10-26
Patel, Kanji (Department: 2624)
Image analysis
Image transformation or preprocessing
C382S274000
Reexamination Certificate
active
07822289
ABSTRACT:
A “Finite Element Preconditioner” provides locally adapted hierarchical basis functions for preconditioning large data optimization problems. For example, a few of the many typical graphics applications that make use of iterative optimization solutions include tone mapping, gradient domain blending, colorization, and scattered data interpolation. Preconditioning image data for such optimization problems allows those image optimization problems to be solved using less computational overhead and therefore to produce better quality image outputs with less computational overhead. The Finite Element Preconditioner evaluates data, such as image data, to adapt hierarchical basis functions to inhomogeneous problems for preconditioning large optimization problems. Specifically, the Finite Element Preconditioner evaluates the local structure of a coefficient matrix derived from the data and performs a recursive set of variable eliminations, combined with a simplification of the resulting coarse level problems to obtain bases better suited for problems with inhomogeneous (spatially varying) data, smoothness, and boundary constraints.
REFERENCES:
patent: 5513120 (1996-04-01), Berlad
patent: 6094511 (2000-07-01), Metcalfe
patent: 6389154 (2002-05-01), Stam
patent: 6856705 (2005-02-01), Perez
patent: 6894720 (2005-05-01), Zhang
patent: 7010174 (2006-03-01), Kang
patent: 7023580 (2006-04-01), Zhang
patent: 7353153 (2008-04-01), Ascenzi et al.
patent: 2005/0104900 (2005-05-01), Toyama
patent: 2005/0243176 (2005-11-01), Wu
patent: 2325837 (1998-02-01), None
Ledda, et al., “Evaluation of Tone Mapping Operators using a High Dynamic Range Display” Evaluation of tone mapping operators using a High Dynamic Range display. ACM Trans. Graph. 24, 3 (Jul. 2005), 640-648.
Aksoylu, et al. “An Odyssey into Local Refinement and Multilevel Preconditioning II: Stabilizing Hierarchical Basis Methods” SIAM Journal on Scientific Computing, 25 (2). pp. 478-498. ISSN 1064-8275, 2003.
Schmidt, et al. “ALBERT: An adaptive hierarchical finite element toolbox” Preprint Jun. 2000 Freiburg, 2000.
Krysl, et al. “Natural Hierarchical Refinement for Finite Element Methods” International Journal for Numerical Methods in Engineering, vol. 56, Num 8, pp. 1109-1124, Feb. 2003.
Bolz, et al. “Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid,” SIGGRAPH, pp. 917-924, 2003.
Agarwala, A., et al. 2004. Interactive digital photomontage. ACM Transactions on Graphics 23, 3 (August), 292-300.
Brand, C. W. 1992. An incomplete factorization preconditioning using repeated red-black ordering. Numer. Math. 61, 433-454.
Briggs, W. L., Henson, V. E., and McCormick, S. F. 2000. A Multigrid Tutorial, second ed. Society for Industrial and Applied Mathematics, Philadelphia.
Crowley, J. L., and Stern, R. M. 1984. Fast computation of the difference of low-pass transform. Tech. Rreport CMU-RI-TR-82-18, Robotics Institute, Carnegie Mellon University, Nov. 1982.
Fattal, R., Lischinski, D., and Werman, M. 2002. Gradient domain high dynamic range compression. ACM Transactions on Graphics (TOG) 21, 3, 249-256.
Feilner, M., et al. 2005. An orthogonal family of quincunx wavelets with continuously adjustable order. IEEE Transactions on Image Processing 14, 4 (April), 499-520.
Gortler, S. J., and Cohen, M. F. 1995. Hierarchical and variational geometric modeling with wavelets. In Symposium on Interactive 3D Graphics, 35-43.
Gremban, K. D. 1996. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University. CMU-CS-96-123.
Kobbelt, L., and Schröder, P. 1998. A multiresolution framework for variational subdivision. ACMTransactions on Graphics 17, 4 (October) 209-237.
Lai, S.-H., and Vemuri, B. C. 1997. Physically based adaptive preconditioning for early vision. IEEE Transactions on Pattern Analysis and Machine Intelligence 19, 6 (June), 594-607.
Levin, A., Lischinski, D., and Weiss, Y. 2004. Colorization using optimization. ACM Transactions on Graphics 23, 3 (August), 689-694.
Levin, A., Zomet, A., Peleg, S., and Weiss, Y. 2004. Seamless image stitching in the gradient domain. In Eighth European Conference on Computer Vision (ECCV 2004), Springer-Verlag, Prague, vol. IV, 377-389.
Notay, Y., and Amar, Z. O. 1997. A nearly optimal preconditioning based on recursive red-black ordering. Numerical Linear Alg. Appl. 4, 369-391.
Pentland, A. P. 1994. Interpolation using wavelet bases. IEEE Transactions on Pattern Analysis and Machine Intelligence 16, 4 (April), 410-414.
Perez, P., Gangnet, M., and Blake, A. 2003. Poisson image editing. ACM Transactions on Graphics 22, 3 (July), 313-318.
Schröder, P., and Sweldens, W. 1995. Spherical wavelets: Efficiently representing functions on the sphere. In Proceedings of SIGGRAPH 95, Computer Graphics Proceedings , Annual Conference Series, 161-172.
Sweldens, W. 1997. The lifting scheme: A construction of second generation wavelets. SIAM J. Math. Anal. 29, 2, 511-546.
Szeliski, R. 1990. Fast surface interpolation using hierarchical basis functions. IEEE Transactions on Pattern Analysis and Machine Intelligence 12, 6 (June), 513-528.
Terzopoulos, D., and Witkin, A. 1988. Physically-based models with rigid and deformable components. IEEE Computer Graphics and Applications 8, 6, 41-51.
Terzopoulos, D. 1986. Regularization of inverse visual problems involving discontinuities. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-8, 4 (July), 413-424.
Yaou, M.-H., and Chang, W.-T. 1994. Fast surface interpolation using multiresolution wavelet transform. IEEE Transactions on Pattern Analysis and Machine Intelligence 16, 7 (July), 673-689.
Zhang, L., et al. 2002. Single view modeling of free-form scenes. Journal of Visualization and Computer Animation 13, 4, 225-235.
Lyon & Harr LLP
Microsoft Corporation
Patel Kanji
Watson Mark A.
LandOfFree
Locally adapted hierarchical basis preconditioning does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Locally adapted hierarchical basis preconditioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Locally adapted hierarchical basis preconditioning will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4151347