FEAT: Summed Area Tables (sat, af_sat) a.k.a integral images

pradeep · pradeep · commit 61ea09115415 · 2015-08-04T19:59:14.000-04:00
diff --git a/docs/details/image.dox b/docs/details/image.dox
@@ -583,6 +583,19 @@ from the other and returns the result.
 
 =======================================================================
 
+\defgroup image_func_sat SAT
+\ingroup imageflt_mat
+
+\brief Summed Area Tables
+
+Given an image \f$ I: (x,y) \mapsto i \f$ where i is pixel intensity at position \f$(x, y)\f$.
+
+\f$S(x, y) = i(x, y) + S(x-1, y) + S(x, y-1) - S(x-1, y-1)\f$
+
+The output array of this function will have \f$ S(x, y) \f$ values at their corresponding locations, \f$(x,y)\f$
+
+=======================================================================
+
 \defgroup image_func_unwrap unwrap
 \ingroup image_mod
 
diff --git a/include/af/image.h b/include/af/image.h
@@ -490,6 +490,17 @@ AFAPI array dog(const array& in, const int radius1, const int radius2);
 AFAPI array unwrap(const array& in, const dim_t wx, const dim_t wy,
                    const dim_t sx, const dim_t sy, const dim_t px=0, const dim_t py=0);
 
+
+/**
+   C++ Interface wrapper for summed area tables
+
+   \param[in]  in is the input array
+   \returns the summed area table of input image
+
+   \ingroup image_func_sat
+*/
+AFAPI array sat(const array& in);
+
 }
 #endif
 
@@ -965,6 +976,18 @@ extern "C" {
     AFAPI af_err af_unwrap(af_array *out, const af_array in, const dim_t wx, const dim_t wy,
                            const dim_t sx, const dim_t sy, const dim_t px, const dim_t py);
 
+    /**
+       C Interface wrapper for summed area tables
+
+       \param[out] out is the summed area table on input image(s)
+       \param[in]  in is the input array
+       \return \ref AF_SUCCESS if the sat computation is successful,
+       otherwise an appropriate error code is returned.
+
+       \ingroup image_func_sat
+    */
+    AFAPI af_err af_sat(af_array *out, const af_array in);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/src/api/c/sat.cpp b/src/api/c/sat.cpp
@@ -0,0 +1,57 @@
+/*******************************************************
+ * Copyright (c) 2014, ArrayFire
+ * All rights reserved.
+ *
+ * This file is distributed under 3-clause BSD license.
+ * The complete license agreement can be obtained at:
+ * http://arrayfire.com/licenses/BSD-3-Clause
+ ********************************************************/
+
+#include <af/defines.h>
+#include <af/image.h>
+#include <handle.hpp>
+#include <err_common.hpp>
+#include <scan.hpp>
+
+using af::dim4;
+using namespace detail;
+
+template<typename To, typename Ti>
+static af_array sat(const af_array& in)
+{
+    const Array<To> input = castArray<To>(in);
+
+    Array<To> hprefix_scan = scan<af_add_t, To, To>(input, 0);
+    Array<To> vprefix_scan = scan<af_add_t, To, To>(hprefix_scan, 1);
+
+    return getHandle<To>(vprefix_scan);
+}
+
+af_err af_sat(af_array* out, const af_array in)
+{
+    try{
+        ArrayInfo info = getInfo(in);
+        const dim4 dims = info.dims();
+
+        ARG_ASSERT(1, (dims.ndims() >= 2));
+
+        af_dtype inputType = info.getType();
+
+        af_array output = 0;
+        switch(inputType) {
+            case f64: output = sat<double, double>(in); break;
+            case f32: output = sat<float , float >(in); break;
+            case s32: output = sat<int   , int   >(in); break;
+            case u32: output = sat<uint  , uint  >(in); break;
+            case  b8: output = sat<int   , char  >(in); break;
+            case  u8: output = sat<uint  , uchar >(in); break;
+            case s64: output = sat<intl  , intl  >(in); break;
+            case u64: output = sat<uintl , uintl >(in); break;
+            default: TYPE_ERROR(1, inputType);
+        }
+        std::swap(*out, output);
+    }
+    CATCHALL;
+
+    return AF_SUCCESS;
+}
diff --git a/src/api/cpp/sat.cpp b/src/api/cpp/sat.cpp
@@ -0,0 +1,24 @@
+/*******************************************************
+ * Copyright (c) 2014, ArrayFire
+ * All rights reserved.
+ *
+ * This file is distributed under 3-clause BSD license.
+ * The complete license agreement can be obtained at:
+ * http://arrayfire.com/licenses/BSD-3-Clause
+ ********************************************************/
+
+#include <af/image.h>
+#include <af/array.h>
+#include "error.hpp"
+
+namespace af
+{
+
+array sat(const array& in)
+{
+    af_array out = 0;
+    AF_THROW(af_sat(&out, in.get()));
+    return array(out);
+}
+
+}
diff --git a/test/sat.cpp b/test/sat.cpp
@@ -0,0 +1,43 @@
+/*******************************************************
+ * Copyright (c) 2014, ArrayFire
+ * All rights reserved.
+ *
+ * This file is distributed under 3-clause BSD license.
+ * The complete license agreement can be obtained at:
+ * http://arrayfire.com/licenses/BSD-3-Clause
+ ********************************************************/
+
+#include <gtest/gtest.h>
+#include <arrayfire.h>
+#include <af/dim4.hpp>
+#include <af/traits.hpp>
+#include <string>
+#include <vector>
+#include <testHelpers.hpp>
+
+using std::string;
+using std::vector;
+
+template<typename T>
+class SAT : public ::testing::Test
+{
+    public:
+        virtual void SetUp() {}
+};
+
+// create a list of types to be tested
+typedef ::testing::Types<float, double, int, uint, char, uchar, uintl, intl> TestTypes;
+
+// register the type list
+TYPED_TEST_CASE(SAT, TestTypes);
+
+TYPED_TEST(SAT, IntegralImage)
+{
+    af::array a = af::randu(530, 671, (af_dtype)af::dtype_traits<TypeParam>::af_type);
+    af::array b = af::accum(a, 0);
+    af::array c = af::accum(b, 1);
+
+    af::array s = af::sat(a);
+
+    EXPECT_EQ(true, af::allTrue<float>(c==s));
+}
