TOP > 外国特許検索 > High-speed high-accuracy matrix singular value decomposition method, program, and device

High-speed high-accuracy matrix singular value decomposition method, program, and device 実績あり

外国特許コード F110005491
整理番号 K07601WO
掲載日 2011年9月6日
出願国 アメリカ合衆国
出願番号 56989805
公報番号 20090028455
公報番号 8306361
出願日 平成17年6月1日(2005.6.1)
公報発行日 平成21年1月29日(2009.1.29)
公報発行日 平成24年11月6日(2012.11.6)
国際出願番号 JP2005010084
国際公開番号 WO2005119507
国際出願日 平成17年6月1日(2005.6.1)
国際公開日 平成17年12月15日(2005.12.15)
優先権データ
  • 特願2004-166437 (2004.6.3) JP
  • 2005WO-JP10084 (2005.6.1) WO
発明の名称 (英語) High-speed high-accuracy matrix singular value decomposition method, program, and device 実績あり
発明の概要(英語) (US8306361)
A singular value decomposition method according to the present invention is a method for performing a singular value decomposition on an arbitrary matrix A using a computer, the method including the steps of: performing an upper bidiagonalization on the matrix A so as to obtain an upper bidiagonal matrix B of the matrix A; obtaining at least one singular value σ of the matrix B as singular values of the matrix A; and obtaining a singular vector of the matrix A for the σ.
The step of obtaining a singular vector of the matrix A includes a step of performing a Twisted decomposition on a matrix BTB-σ2I (where I is a unit matrix) by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB.
特許請求の範囲(英語) [claim1]
1. A method for restoring a three-dimensional image from a plurality of two-dimensional images of an object, the method comprising the steps of: extracting coordinates dij (xij, yij) of feature points i (i=1, . . . , n, where n is an integer greater than or equal to 2) in two-dimensional images j (j=1, . . . , m, where m is an integer greater than or equal to 3); and
computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional coordinates based on the two-dimensional coordinates dij (xij, yij) of the feature points,
wherein
the step of computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional coordinates includes the steps of: performing an upper bidiagonalization on a matrix D so as to obtain an upper bidiagonal matrix B of the matrix D, the matrix D being defined as
(Equation image 18 not included in text) obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D;
obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3;
computing a matrix E satisfying E=CCT for a matrix C such that M=M'C, where M'=L' (SIGMA ')1/2, SIGMA ' is a 3 * 3 matrix having sigma 1, sigma 2 and sigma 3 as diagonal elements and the other elements being 0, and L' is a matrix having singular vectors of the matrix D corresponding to sigma 1, sigma 2 and sigma 3 arranged from a left side in this order;
computing the matrix C from the matrix E; and
computing the three-dimensional coordinates si (Xi, Yi, Zi) and the matrix M representing the transformation from the matrix C,
wherein
the step of obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3 includes a step of performing a Twisted decomposition on a matrix BTB-sigma j2I by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix.
[claim2]
2. A method for searching information relating to a given keyword, the information being included in a given document, the method comprising the steps of: receiving query vector q corresponding to the keyword;
performing an upper bidiagonalization on an index word document matrix D corresponding to the document so as to obtain an upper bidiagonal matrix B of the matrix D;
obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D;
selecting k such that k<r;
computing an approximate matrix Dk of the matrix D, the matrix Dk being defined as Dk=UkSIGMA kVkT by using a matrix SIGMA k having sigma 1, sigma 2, . . . , sigma k as diagonal elements and the other elements being 0, and left and right orthogonal matrices Uk, Vk having only singular vectors corresponding to sigma 1, sigma 2, . . . , sigma k arranged from a left side in this order;
computing a similarity between the matrix Dk and the query vector q; and
outputting a search result based on the computed similarity,
wherein
the step of obtaining left and right orthogonal matrices Uk, Vk of a matrix Dk includes a step of performing a Twisted decomposition on a matrix BTB-sigma j2I (j=1, 2, . . . , k) by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix.
[claim3]
3. A non-transitory computer readable medium storing a program for causing a computer to execute an image restoring process for restoring a three-dimensional image from a plurality of two-dimensional images of an object, the image restoring process including the steps of: extracting coordinates dij (xij, yij) of feature points i (i=1, . . . , n, where n is an integer greater than or equal to 2) in two-dimensional images j (j=1, . . . , m, where m is an integer greater than or equal to 3); and
computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional coordinates based on the two-dimensional coordinates dij (xij, yij) of the feature points,
wherein
the step of computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional coordinates includes the steps of: performing an upper bidiagonalization on a matrix D so as to obtain an upper bidiagonal matrix B of the matrix D, the matrix D being defined as
(Equation image 19 not included in text) obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D;
obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3;
computing a matrix E satisfying E=CCT for a matrix C such that M=M'C, where M'=(L'(SIGMA ')1/2, SIGMA ' is a 3 * 3 matrix having sigma 1, sigma 2 and sigma 3 as diagonal elements and the other elements being 0, and L' is a matrix having singular vectors of the matrix D corresponding to sigma 1, sigma 2 and sigma 3 arranged from a left side in this order;
computing the matrix C from the matrix E; and
computing the three-dimensional coordinates si (Xi, Yi, Zi) and the matrix M representing the transformation from the matrix C,
wherein
the step of obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3 includes a step of performing a Twisted decomposition on a matrix BTB-sigma j2I by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix.
[claim4]
4. A non-transitory computer readable medium storing a program for causing a computer to execute a document search process for searching information relating to a given keyword, the information being included in a given document, the document search process including the steps of: receiving query vector q corresponding to the keyword;
performing an upper bidiagonalization on an index word document matrix D corresponding to the document so as to obtain an upper bidiagonal matrix B of the matrix D;
obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D;
selecting k such that k<r;
computing an approximate matrix Dk of the matrix D, the matrix Dk being defined as Dk=UkSIGMA kVkT by using a matrix SIGMA k having sigma 1, sigma 2, . . . , sigma k as diagonal elements and the other elements being 0, and left and right orthogonal matrices Uk, Vk having only singular vectors corresponding to sigma 1, sigma 2, . . . , sigma k arranged from a left side in this order;
computing a similarity between the matrix Dk and the query vector q; and
outputting a search result based on the computed similarity,
wherein
the step of obtaining left and right orthogonal matrices Uk, Vk of the matrix Dk includes a step of performing a Twisted decomposition on a matrix BTB-sigma j2I (j=1, 2, . . . , k) by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix.
[claim5]
5. An apparatus for restoring a three-dimensional image from a plurality of two-dimensional images of an object, the apparatus comprising: means for receiving m number (m is an integer greater than or equal to 3) of two-dimensional images;
means for extracting coordinates dij (xij, yij) of feature points i (i=1, . . . , n, where n is an integer greater than or equal to 2) in two-dimensional images j (j=1, . . . , m); and
means for computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional coordinates based on the two-dimensional coordinates dij (xij, yij) of the feature points,
wherein
the means for computing three-dimensional coordinates si (Xi, Yi, Zi) of the feature points and a matrix M representing a transformation from two-dimensional coordinates to three-dimensional coordinates includes: means for performing an upper bidiagonalization on a matrix D so as to obtain an upper bidiagonal matrix B of the matrix D, the matrix D being defined as
(Equation image 20 not included in text) means for obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D;
means for obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3;
means for computing a matrix E satisfying E=CCT for a matrix C such that M=M'C, where M'=L'(SIGMA ')1/2, SIGMA ' is a 3 * 3 matrix having sigma 1, sigma 2 and sigma 3 as diagonal elements and the other elements being 0, and L' is a matrix having singular vectors of the matrix D corresponding to sigma 1, sigma 2 and sigma 3 arranged from a left side in this order;
means for computing the matrix C from the matrix E; and
means for computing the three-dimensional coordinates si (Xi, Yi, Zi) and the matrix M representing the transformation from the matrix C,
wherein
the means for obtaining singular vectors of the matrix D for sigma 1, sigma 2 and sigma 3 includes means for performing a Twisted decomposition on a matrix BTB-sigma j2I by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix.
[claim6]
6. An apparatus for searching information relating to a given keyword, the information being included in a given document, the apparatus comprising: means for receiving query vector q corresponding to the keyword;
means for performing an upper bidiagonalization on an index word document matrix D corresponding to the document so as to obtain an upper bidiagonal matrix B of the matrix D;
means for obtaining singular values sigma j (sigma 1 >= sigma 2 >= . . . >= sigma r>0, where r is equal to a rank of the matrix D) of the matrix B as singular values of the matrix D;
means for selecting k such that k<r;
means for computing an approximate matrix Dk of the matrix D, the matrix Dk being defined as Dk=UkSIGMA kVkT by using a matrix SIGMA k having sigma 1, sigma 2, . . . , sigma k as diagonal elements and the other elements being 0, and left and right orthogonal matrices Uk, Vk having only singular vectors corresponding to sigma 1, sigma 2, . . . , sigma k arranged from a left side in this order;
means for computing a similarity between the matrix Dk and the query vector q; and
means for outputting a search result based on the computed similarity,
wherein
the means for obtaining left and right orthogonal matrices Uk, Vk of the matrix Dk includes means for performing a Twisted decomposition on a matrix BTB-sigma j2I (j=1, 2, . . . , k) by using a Miura inverse transformation, an sdLVvs transformation, an rdLVvs transformation and a Miura transformation so as to diagonalize a matrix BTB, where I is a unit matrix.
  • 発明者/出願人(英語)
  • NAKAMURA YOSHIMASA
  • IWASAKI MASASHI
  • SAKANO SHINYA
  • JAPAN SCIENCE AND TECHNOLOGY AGENCY
国際特許分類(IPC)
米国特許分類/主・副
  • G06F017/16
  • G06T007/00R7
参考情報 (研究プロジェクト等) PRESTO The Innovation of Simulation Technology and the Construction of Foundations for its Practical Use AREA
ライセンスをご希望の方、特許の内容に興味を持たれた方は、問合せボタンを押してください。

PAGE TOP

close
close
close
close
close
close