{"id":22983,"url":"https://patchwork.libcamera.org/api/1.1/patches/22983/?format=json","web_url":"https://patchwork.libcamera.org/patch/22983/","project":{"id":1,"url":"https://patchwork.libcamera.org/api/1.1/projects/1/?format=json","name":"libcamera","link_name":"libcamera","list_id":"libcamera_core","list_email":"libcamera-devel@lists.libcamera.org","web_url":"","scm_url":"","webscm_url":""},"msgid":"<20250319161152.63625-6-stefan.klug@ideasonboard.com>","date":"2025-03-19T16:11:10","name":"[v2,05/17] libcamera: matrix: Add inverse() function","commit_ref":null,"pull_url":null,"state":"superseded","archived":false,"hash":"2e6f0c5fece09a29410f9bc0c8cd117cc447e411","submitter":{"id":184,"url":"https://patchwork.libcamera.org/api/1.1/people/184/?format=json","name":"Stefan Klug","email":"stefan.klug@ideasonboard.com"},"delegate":null,"mbox":"https://patchwork.libcamera.org/patch/22983/mbox/","series":[{"id":5071,"url":"https://patchwork.libcamera.org/api/1.1/series/5071/?format=json","web_url":"https://patchwork.libcamera.org/project/libcamera/list/?series=5071","date":"2025-03-19T16:11:05","name":"Some rkisp1 awb improvements","version":2,"mbox":"https://patchwork.libcamera.org/series/5071/mbox/"}],"comments":"https://patchwork.libcamera.org/api/patches/22983/comments/","check":"pending","checks":"https://patchwork.libcamera.org/api/patches/22983/checks/","tags":{},"headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id 018E2C32FE\n\tfor ;\n\tWed, 19 Mar 2025 16:12:13 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 8A92B6895B;\n\tWed, 19 Mar 2025 17:12:13 +0100 (CET)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id DE4D268950\n\tfor ;\n\tWed, 19 Mar 2025 17:12:11 +0100 (CET)","from ideasonboard.com (unknown\n\t[IPv6:2a00:6020:448c:6c00:760:e5ca:4814:99c7])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id EC4588FA;\n\tWed, 19 Mar 2025 17:10:28 +0100 (CET)"],"Authentication-Results":"lancelot.ideasonboard.com; dkim=pass (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"uvH2Li6K\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1742400629;\n\tbh=Gfx7x+E8Sx24+3cf5pWOkHZEsFcd/OJpxqWgEUGDWOQ=;\n\th=From:To:Cc:Subject:Date:In-Reply-To:References:From;\n\tb=uvH2Li6KYtr+IhpDRImz0Kft4waOW8/iusEVnphGvEtIowZy6A1JOygQq54tJUmAg\n\tZwtZMnjU95P3xEzKvjyBlx13xwWd0FdPgifZNbta1p9Pt0v8vB9UENBJPENtXIm1SQ\n\tGiDyuQO0sKUPPsPjTUId5nyCzeeazWIQkJFBHNRA=","From":"Stefan Klug ","To":"libcamera-devel@lists.libcamera.org","Cc":"Stefan Klug ,\n\tLaurent Pinchart ","Subject":"[PATCH v2 05/17] libcamera: matrix: Add inverse() function","Date":"Wed, 19 Mar 2025 17:11:10 +0100","Message-ID":"<20250319161152.63625-6-stefan.klug@ideasonboard.com>","X-Mailer":"git-send-email 2.43.0","In-Reply-To":"<20250319161152.63625-1-stefan.klug@ideasonboard.com>","References":"<20250319161152.63625-1-stefan.klug@ideasonboard.com>","MIME-Version":"1.0","Content-Transfer-Encoding":"8bit","X-BeenThere":"libcamera-devel@lists.libcamera.org","X-Mailman-Version":"2.1.29","Precedence":"list","List-Id":"","List-Unsubscribe":",\n\t","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n\t","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "},"content":"For calculations in upcoming algorithm patches, the inverse of a matrix\nis required. Add an implementation of the inverse() function for square\nmatrices.\n\nSigned-off-by: Stefan Klug \nSigned-off-by: Laurent Pinchart \n\n---\n\nChanges in v2:\n- Replaced the implementation by a generic one provided by Laurent that\n supports arbitrary square matrices instead of 2x2 and 3x3 only.\n- Moved the implementation into the cpp file.\n---\n include/libcamera/internal/matrix.h | 16 +++\n src/libcamera/matrix.cpp | 160 ++++++++++++++++++++++++++++\n 2 files changed, 176 insertions(+)","diff":"diff --git a/include/libcamera/internal/matrix.h b/include/libcamera/internal/matrix.h\nindex 9b80521e3cb0..6e3c190286fe 100644\n--- a/include/libcamera/internal/matrix.h\n+++ b/include/libcamera/internal/matrix.h\n@@ -19,6 +19,11 @@ namespace libcamera {\n \n LOG_DECLARE_CATEGORY(Matrix)\n \n+#ifndef __DOXYGEN__\n+template\n+bool matrixInvert(Span dataIn, Span dataOut, unsigned int dim);\n+#endif /* __DOXYGEN__ */\n+\n template\n class Matrix\n {\n@@ -88,6 +93,17 @@ public:\n \t\treturn *this;\n \t}\n \n+\tMatrix inverse(bool *ok = nullptr) const\n+\t{\n+\t\tstatic_assert(Rows == Cols, \"Matrix must be square\");\n+\n+\t\tMatrix inverse;\n+\t\tbool res = matrixInvert(Span(data_), Span(inverse.data_), Rows);\n+\t\tif (ok)\n+\t\t\t*ok = res;\n+\t\treturn inverse;\n+\t}\n+\n private:\n \tstd::array data_{};\n };\ndiff --git a/src/libcamera/matrix.cpp b/src/libcamera/matrix.cpp\nindex 6dca7498cab3..8590f8efeff3 100644\n--- a/src/libcamera/matrix.cpp\n+++ b/src/libcamera/matrix.cpp\n@@ -7,6 +7,12 @@\n \n #include \"libcamera/internal/matrix.h\"\n \n+#include \n+#include \n+#include \n+#include \n+#include \n+\n #include \n \n /**\n@@ -87,6 +93,20 @@ LOG_DEFINE_CATEGORY(Matrix)\n * \\return Row \\a i from the matrix, as a Span\n */\n \n+/**\n+ * \\fn Matrix::inverse(bool *ok) const\n+ * \\param[out] ok Indicate if the matrix was successfully inverted\n+ * \\brief Compute the inverse of the matrix\n+ *\n+ * This function computes the inverse of the matrix. It is only implemented for\n+ * matrices of float and double types. If \\a ok is provided it will be set to a\n+ * boolean value to indicate of the inversion was successful. This can be used\n+ * to check if the matrix is singular, in which case the function will return\n+ * an identity matrix.\n+ *\n+ * \\return The inverse of the matrix\n+ */\n+\n /**\n * \\fn Matrix::operator[](size_t i)\n * \\copydoc Matrix::operator[](size_t i) const\n@@ -142,6 +162,146 @@ LOG_DEFINE_CATEGORY(Matrix)\n */\n \n #ifndef __DOXYGEN__\n+template\n+bool matrixInvert(Span dataIn, Span dataOut, unsigned int dim)\n+{\n+\t/*\n+\t * Convenience class to access matrix data, providing a row-major (i,j)\n+\t * element accessor through the call operator, and the ability to swap\n+\t * rows without modifying the backing storage.\n+\t */\n+\tclass MatrixAccessor\n+\t{\n+\tpublic:\n+\t\tMatrixAccessor(Span data, unsigned int rows, unsigned int cols)\n+\t\t\t: data_(data), swap_(rows), rows_(rows), cols_(cols)\n+\t\t{\n+\t\t\tstd::iota(swap_.begin(), swap_.end(), T{ 0 });\n+\t\t}\n+\n+\t\tT &operator()(unsigned int row, unsigned int col)\n+\t\t{\n+\t\t\tassert(row < rows_ && col < cols_);\n+\t\t\treturn data_[index(row, col)];\n+\t\t}\n+\n+\t\tvoid swap(unsigned int a, unsigned int b)\n+\t\t{\n+\t\t\tassert(a < rows_ && a < cols_);\n+\t\t\tstd::swap(swap_[a], swap_[b]);\n+\t\t}\n+\n+\tprivate:\n+\t\tunsigned int index(unsigned int row, unsigned int col) const\n+\t\t{\n+\t\t\treturn swap_[row] * cols_ + col;\n+\t\t}\n+\n+\t\tSpan data_;\n+\t\tstd::vector swap_;\n+\t\tunsigned int rows_;\n+\t\tunsigned int cols_;\n+\t};\n+\n+\t/*\n+\t * Matrix inversion using Gaussian elimination.\n+\t *\n+\t * Start by augmenting the original matrix with an identiy matrix of\n+\t * the same size.\n+\t */\n+\tstd::vector data(dim * dim * 2);\n+\tMatrixAccessor matrix(data, dim, dim * 2);\n+\n+\tfor (unsigned int i = 0; i < dim; ++i) {\n+\t\tfor (unsigned int j = 0; j < dim; ++j)\n+\t\t\tmatrix(i, j) = dataIn[i * dim + j];\n+\t\tmatrix(i, i + dim) = T{ 1 };\n+\t}\n+\n+\t/* Start by triangularizing the input . */\n+\tfor (unsigned int pivot = 0; pivot < dim; ++pivot) {\n+\t\t/*\n+\t\t * Locate the next pivot. To improve numerical stability, use\n+\t\t * the row with the largest value in the pivot's column.\n+\t\t */\n+\t\tunsigned int row;\n+\t\tT maxValue{ 0 };\n+\n+\t\tfor (unsigned int i = pivot; i < dim; ++i) {\n+\t\t\tT value = std::abs(matrix(i, pivot));\n+\t\t\tif (maxValue < value) {\n+\t\t\t\tmaxValue = value;\n+\t\t\t\trow = i;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/*\n+\t\t * If no pivot is found in the column, the matrix is not\n+\t\t * invertible. Return an identity matrix.\n+\t\t */\n+\t\tif (maxValue == 0) {\n+\t\t\tstd::fill(dataOut.begin(), dataOut.end(), T{ 0 });\n+\t\t\tfor (unsigned int i = 0; i < dim; ++i)\n+\t\t\t\tdataOut[i * dim + i] = T{ 1 };\n+\t\t\treturn false;\n+\t\t}\n+\n+\t\t/* Swap rows to bring the pivot in the right location. */\n+\t\tmatrix.swap(pivot, row);\n+\n+\t\t/* Process all rows below the pivot to zero the pivot column. */\n+\t\tconst T pivotValue = matrix(pivot, pivot);\n+\n+\t\tfor (unsigned int i = pivot + 1; i < dim; ++i) {\n+\t\t\tconst T factor = matrix(i, pivot) / pivotValue;\n+\n+\t\t\t/*\n+\t\t\t * We know the element in the pivot column will be 0,\n+\t\t\t * hardcode it instead of computing it.\n+\t\t\t */\n+\t\t\tmatrix(i, pivot) = T{ 0 };\n+\n+\t\t\tfor (unsigned int j = pivot + 1; j < dim * 2; ++j)\n+\t\t\t\tmatrix(i, j) -= matrix(pivot, j) * factor;\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * Then diagonalize the input, walking the diagonal backwards. There's\n+\t * no need to update the input matrix, as all the values we would write\n+\t * in the top-right triangle aren't used in further calculations (and\n+\t * would all by definition be zero).\n+\t */\n+\tfor (unsigned int pivot = dim - 1; pivot > 0; --pivot) {\n+\t\tconst T pivotValue = matrix(pivot, pivot);\n+\n+\t\tfor (unsigned int i = 0; i < pivot; ++i) {\n+\t\t\tconst T factor = matrix(i, pivot) / pivotValue;\n+\n+\t\t\tfor (unsigned int j = dim; j < dim * 2; ++j)\n+\t\t\t\tmatrix(i, j) -= matrix(pivot, j) * factor;\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * Finally, normalize the diagonal and store the result in the output\n+\t * data.\n+\t */\n+\tfor (unsigned int i = 0; i < dim; ++i) {\n+\t\tconst T factor = matrix(i, i);\n+\n+\t\tfor (unsigned int j = 0; j < dim; ++j)\n+\t\t\tdataOut[i * dim + j] = matrix(i, j + dim) / factor;\n+\t}\n+\n+\treturn true;\n+}\n+\n+template bool matrixInvert(Span dataIn, Span dataOut,\n+\t\t\t\t unsigned int dim);\n+template bool matrixInvert(Span data, Span dataOut,\n+\t\t\t\t unsigned int dim);\n+\n /*\n * The YAML data shall be a list of numerical values. Its size shall be equal\n * to the product of the number of rows and columns of the matrix (Rows x\n","prefixes":["v2","05/17"]}