Use block storage for contour points

mshabunin · mshabunin · commit 5f35ea3dfa71 · 2025-01-26T22:28:35.000+03:00
diff --git a/modules/imgproc/src/contours_common.hpp b/modules/imgproc/src/contours_common.hpp
@@ -27,6 +27,48 @@ inline schar clamp_direction(schar dir)
     return std::min(dir, (schar)15);
 }
 
+// BLOCK_SIZE - number of elements in a block
+template <typename T, size_t BLOCK_SIZE = 1024>
+class BlockStorage {
+public:
+    using value_type = T;
+    using block_type = T*;
+
+    BlockStorage() : sz(0)
+    {
+        blocks.push_back(new value_type[BLOCK_SIZE]);
+    }
+
+    // Add an element to the storage
+    void push_back(const T& value) {
+        if ((sz > 0) && (sz % BLOCK_SIZE == 0)) {
+            blocks.push_back(new value_type[BLOCK_SIZE]);
+        }
+        block_type & cur_block = *(blocks.end() - 1);
+        cur_block[sz % BLOCK_SIZE] = value;
+        ++sz;
+    }
+
+    size_t size() const { return sz; }
+
+    const value_type & at(size_t index) const {
+        const block_type & cur_block = blocks.at(index / BLOCK_SIZE);
+        return cur_block[index % BLOCK_SIZE];
+    }
+
+    ~BlockStorage() {
+        for(const auto & block : blocks) {
+            delete[] block;
+        }
+    }
+
+private:
+
+    std::vector<value_type*> blocks;
+    size_t sz;
+};
+
+
 
 template <typename T, size_t CAPACITY = 4096>
 class ArenaStackBuffer
@@ -210,7 +252,7 @@ class ArenaDynamicBufferIndexed
                 index_storage_t _index;
         };
     public:
-        ArenaDynamicBufferIndexed(void) {_buffer.reserve(CAPACITY/sizeof(T));}
+        ArenaDynamicBufferIndexed(void) {_buffer.reserve(6000000);}
         ArenaDynamicBufferIndexed(const ArenaDynamicBufferIndexed&) = delete;
         ArenaDynamicBufferIndexed(ArenaDynamicBufferIndexed&&) noexcept = delete;
         ~ArenaDynamicBufferIndexed() = default;
@@ -437,8 +479,8 @@ class TreeNode
     T body;
 
 public:
-    TreeNode(int self, ContourArena* arena) :
-        self_(self), parent(-1), first_child(-1), prev(-1), next(-1), ctable_next(-1), body(arena)
+    TreeNode(int self, T body_) :
+        self_(self), parent(-1), first_child(-1), prev(-1), next(-1), ctable_next(-1), body(body_)
     {
         CV_Assert(self >= 0);
     }
@@ -456,27 +498,28 @@ template <typename T>
 class Tree
 {
 public:
-    Tree(ContourArena* contoursArena):_contoursArena(contoursArena) {}
+    Tree() {}
+    // Tree(ContourArena* contoursArena):_contoursArena(contoursArena) {}
     Tree(const Tree&) = delete;
     Tree(Tree&&) = delete;
     Tree& operator=(const Tree&) = delete;
     Tree& operator=(Tree&&) = delete;
     ~Tree() = default;
+// private:
+    // ContourArena* _contoursArena;
+    // ArenaStackBuffer<TreeNode<T> > _treeNodesArena;
+// public:
+    // typename vectorWithArena<int>::arena_t _treeIteratorArena;
 private:
-    ContourArena* _contoursArena;
-    ArenaStackBuffer<TreeNode<T> > _treeNodesArena;
-public:
-    typename vectorWithArena<int>::arena_t _treeIteratorArena;
-private:
-    typedef typename ArenaStackBuffer<TreeNode<T> >::Item node_t;
-    std::vector<node_t> nodes;
+    // typedef typename ArenaStackBuffer<TreeNode<T> >::Item node_t;
+    std::vector<TreeNode<T>> nodes;
 
 public:
-    TreeNode<T>& newElem()
+    TreeNode<T>& newElem(T && body_)
     {
         const size_t idx = nodes.size();
         CV_DbgAssert(idx < (size_t)std::numeric_limits<int>::max());
-        nodes.emplace_back(std::move(_treeNodesArena.newItem((int)idx, _contoursArena)));
+        nodes.push_back(TreeNode<T>((int)idx, body_));
         return nodes[idx];
     }
     TreeNode<T>& elem(int idx)
@@ -577,42 +620,53 @@ class TreeIterator
 class Contour
 {
 public:
-    ContourArena* _arena;
+    BlockStorage<cv::Point> & storage;
+    size_t start, end;
     cv::Rect brect;
     cv::Point origin;
-    ContourPointsStorage pts;
+    // ContourPointsStorage pts;
     std::vector<schar> codes;
     bool isHole;
     bool isChain;
 
-    explicit Contour(ContourArena* arena) : _arena(arena), isHole(false), isChain(false) {
-    }
-    Contour(const Contour&) = delete;
-    Contour(Contour&& other) noexcept {*this = std::move(other);}
-    Contour& operator=(const Contour&) = delete;
-    Contour& operator=(Contour&& other) noexcept {
-        if (&other != this) {
-            std::swap(this->_arena, other._arena);
-            std::swap(this->brect, other.brect);
-            std::swap(this->origin, other.origin);
-            std::swap(this->pts, other.pts);
-            std::swap(this->codes, other.codes);
-            std::swap(this->isHole, other.isHole);
-            std::swap(this->isChain, other.isChain);
-        }
-        return *this;
+    explicit Contour(BlockStorage<cv::Point, 1024> & storage_) : storage(storage_), start(0), end(0), isHole(false), isChain(false) {
     }
+    // Contour(const Contour&) = delete;
+    // Contour(Contour&& other) noexcept {*this = std::move(other);}
+    // Contour& operator=(const Contour&) = delete;
+    // Contour& operator=(Contour&& other) noexcept {
+    //     if (&other != this) {
+    //         std::swap(this->storage, other.storage);
+    //         std::swap(this->brect, other.brect);
+    //         std::swap(this->origin, other.origin);
+    //         // std::swap(this->pts, other.pts);
+    //         std::swap(this->codes, other.codes);
+    //         std::swap(this->isHole, other.isHole);
+    //         std::swap(this->isChain, other.isChain);
+    //     }
+    //     return *this;
+    // }
     ~Contour() {
-      _arena->releaseItems(pts);
+    //   _arena->releaseItems(pts);
     }
     void updateBoundingRect() {}
     bool isEmpty() const
     {
-        return pts.size() == 0 && codes.size() == 0;
+        // return pts.size() == 0 && codes.size() == 0;
+        return end - start == 0;
     }
     size_t size() const
     {
-        return isChain ? codes.size() : pts.size();
+        // return isChain ? codes.size() : pts.size();
+        return end - start;
+    }
+    void addPoint(const Point& pt)
+    {
+        if (isEmpty()) {
+            start = storage.size();
+        }
+        storage.push_back(pt);
+        end = storage.size();
     }
     void copyTo(void* data) const
     {
@@ -624,14 +678,10 @@ class Contour
         }
         else
         {
-          unsigned char* dst = reinterpret_cast<unsigned char*>(data);
-          memcpy(dst, &_arena->get(*pts.begin()), pts.size()*sizeof(Point));
-          /*for(auto& it : pts)
-          {
-            const Point& point = _arena->get(it);
-            memcpy(dst, &point, sizeof(point));
-            dst += sizeof(point);
-          }*/
+            for (size_t i = start; i < end; i++)
+            {
+                ((Point*)data)[i - start] = storage.at(i);
+            }
         }
     }
 };
diff --git a/modules/imgproc/src/contours_link.cpp b/modules/imgproc/src/contours_link.cpp
@@ -84,17 +84,18 @@ class LinkRunner
         ICV_CONNECTING_BELOW = -1,
     };
 
-    ContourArena arena;
     CTree tree;
 
     vector<LRP> rns;
     vector<int> ext_rns;
     vector<int> int_rns;
 
+    BlockStorage<Point, 1024> storage;
+
 public:
-    LinkRunner():tree(&arena)
+    LinkRunner():tree()
     {
-        tree.newElem();
+        tree.newElem(Contour(storage));
         rns.reserve(100);
     }
     void process(Mat& image);
@@ -118,12 +119,12 @@ void LinkRunner::convertLinks(int& first, int& prev, bool isHole)
         if (rns[cur].link == -1)
             continue;
 
-        CNode& node = tree.newElem();
+        CNode& node = tree.newElem(Contour(storage));
         node.body.isHole = isHole;
 
         do
         {
-            node.body.pts.emplace_back(arena.newItem(rns[cur].pt));
+            node.body.addPoint(rns[cur].pt);
             int p_temp = cur;
             cur = rns[cur].link;
             rns[p_temp].link = -1;
diff --git a/modules/imgproc/src/contours_new.cpp b/modules/imgproc/src/contours_new.cpp
@@ -170,8 +170,7 @@ static bool icvTraceContour(Mat& image, const Point& start, const Point& end, bo
 }
 
 template <typename T>
-static void icvFetchContourEx(ContourArena& arena,
-                              Mat& image,
+static void icvFetchContourEx(Mat& image,
                               const Point& start,
                               T nbd,
                               Contour& res_contour,
@@ -198,7 +197,7 @@ static void icvFetchContourEx(ContourArena& arena,
         Trait<T>::setRightFlag(i0, i0, nbd);
         if (!res_contour.isChain)
         {
-            res_contour.pts.emplace_back(arena.newItem(pt));
+            res_contour.addPoint(pt);
         }
     }
     else
@@ -237,7 +236,7 @@ static void icvFetchContourEx(ContourArena& arena,
             }
             else if (s != prev_s || isDirect)
             {
-                res_contour.pts.emplace_back(arena.newItem(pt));
+                res_contour.addPoint(pt);
             }
 
             if (s != prev_s)
@@ -282,7 +281,9 @@ static void icvFetchContourEx(ContourArena& arena,
 // It supports both hierarchical and plane variants of Suzuki algorithm.
 struct ContourScanner_
 {
-    ContourArena arena;
+    // ContourArena arena;
+    BlockStorage<Point, 1024> storage;
+
     Mat image;
     Point offset;  // ROI offset: coordinates, added to each contour point
     Point pt;  // current scanner position
@@ -295,7 +296,7 @@ struct ContourScanner_
     array<int, 128> ctable;
 
 public:
-    ContourScanner_():tree(&arena) {}
+    ContourScanner_() {}
     ~ContourScanner_() {}
     inline bool isInt() const
     {
@@ -351,7 +352,7 @@ shared_ptr<ContourScanner_> ContourScanner_::create(Mat img, int mode, int metho
     scanner->pt = Point(1, 1);
     scanner->lnbd = Point(0, 1);
     scanner->nbd = 2;
-    CNode& root = scanner->tree.newElem();
+    CNode& root = scanner->tree.newElem(Contour(scanner->storage));
     CV_Assert(root.self() == 0);
     root.body.isHole = true;
     root.body.brect = Rect(Point(0, 0), size);
@@ -369,13 +370,13 @@ CNode& ContourScanner_::makeContour(schar& nbd_, const bool is_hole, const int x
 
     const Point start_pt(x - (is_hole ? 1 : 0), y);
 
-    CNode& res = tree.newElem();
+    CNode& res = tree.newElem(Contour(storage));
     res.body.isHole = is_hole;
     res.body.isChain = isChain;
     res.body.origin = start_pt + offset;
     if (isSimple())
     {
-        icvFetchContourEx<schar>(this->arena, this->image, start_pt, MASK8_NEW, res.body, isDirect);
+        icvFetchContourEx<schar>(this->image, start_pt, MASK8_NEW, res.body, isDirect);
     }
     else
     {
@@ -384,7 +385,7 @@ CNode& ContourScanner_::makeContour(schar& nbd_, const bool is_hole, const int x
         {
             const int start_val = this->image.at<int>(start_pt);
             lval = start_val & MASK8_LVAL;
-            icvFetchContourEx<int>(this->arena, this->image, start_pt, 0, res.body, isDirect);
+            icvFetchContourEx<int>(this->image, start_pt, 0, res.body, isDirect);
         }
         else
         {
@@ -393,19 +394,19 @@ CNode& ContourScanner_::makeContour(schar& nbd_, const bool is_hole, const int x
             nbd_ = (nbd_ + 1) & MASK8_LVAL;
             if (nbd_ == 0)
                 nbd_ = MASK8_BLACK | MASK8_NEW;
-            icvFetchContourEx<schar>(this->arena, this->image, start_pt, lval, res.body, isDirect);
+            icvFetchContourEx<schar>(this->image, start_pt, lval, res.body, isDirect);
         }
         res.body.brect.x -= this->offset.x;
         res.body.brect.y -= this->offset.y;
         res.ctable_next = this->ctable[lval];
         this->ctable[lval] = res.self();
     }
-    const Point prev_origin = res.body.origin;
+    // const Point prev_origin = res.body.origin;
     res.body.origin = start_pt;
     if (this->approx_method1 != this->approx_method2)
     {
         CV_Assert(res.body.isChain);
-        approximateChainTC89(arena, res.body.codes, prev_origin, this->approx_method2, res.body.pts);
+        // approximateChainTC89(arena, res.body.codes, prev_origin, this->approx_method2, res.body.pts);
         res.body.isChain = false;
     }
     return res;

Original file line number	Diff line number	Diff line change
`@@ -170,8 +170,7 @@ static bool icvTraceContour(Mat& image, const Point& start, const Point& end, bo`
`170`	`170`	`}`
`171`	`171`
`172`	`172`	`template <typename T>`
`173`		`-static void icvFetchContourEx(ContourArena& arena,`
`174`		`- Mat& image,`
	`173`	`+static void icvFetchContourEx(Mat& image,`
`175`	`174`	`const Point& start,`
`176`	`175`	`T nbd,`
`177`	`176`	`Contour& res_contour,`
`@@ -198,7 +197,7 @@ static void icvFetchContourEx(ContourArena& arena,`
`198`	`197`	`Trait<T>::setRightFlag(i0, i0, nbd);`
`199`	`198`	`if (!res_contour.isChain)`
`200`	`199`	`{`
`201`		`- res_contour.pts.emplace_back(arena.newItem(pt));`
	`200`	`+ res_contour.addPoint(pt);`
`202`	`201`	`}`
`203`	`202`	`}`
`204`	`203`	`else`
`@@ -237,7 +236,7 @@ static void icvFetchContourEx(ContourArena& arena,`
`237`	`236`	`}`
`238`	`237`	`else if (s != prev_s \|\| isDirect)`
`239`	`238`	`{`
`240`		`- res_contour.pts.emplace_back(arena.newItem(pt));`
	`239`	`+ res_contour.addPoint(pt);`
`241`	`240`	`}`
`242`	`241`
`243`	`242`	`if (s != prev_s)`
`@@ -282,7 +281,9 @@ static void icvFetchContourEx(ContourArena& arena,`
`282`	`281`	`// It supports both hierarchical and plane variants of Suzuki algorithm.`
`283`	`282`	`struct ContourScanner_`
`284`	`283`	`{`
`285`		`- ContourArena arena;`
	`284`	`+ // ContourArena arena;`
	`285`	`+ BlockStorage<Point, 1024> storage;`
	`286`	`+`
`286`	`287`	`Mat image;`
`287`	`288`	`Point offset; // ROI offset: coordinates, added to each contour point`
`288`	`289`	`Point pt; // current scanner position`
`@@ -295,7 +296,7 @@ struct ContourScanner_`
`295`	`296`	`array<int, 128> ctable;`
`296`	`297`
`297`	`298`	`public:`
`298`		`- ContourScanner_():tree(&arena) {}`
	`299`	`+ ContourScanner_() {}`
`299`	`300`	`~ContourScanner_() {}`
`300`	`301`	`inline bool isInt() const`
`301`	`302`	`{`
`@@ -351,7 +352,7 @@ shared_ptr<ContourScanner_> ContourScanner_::create(Mat img, int mode, int metho`
`351`	`352`	`scanner->pt = Point(1, 1);`
`352`	`353`	`scanner->lnbd = Point(0, 1);`
`353`	`354`	`scanner->nbd = 2;`
`354`		`- CNode& root = scanner->tree.newElem();`
	`355`	`+ CNode& root = scanner->tree.newElem(Contour(scanner->storage));`
`355`	`356`	`CV_Assert(root.self() == 0);`
`356`	`357`	`root.body.isHole = true;`
`357`	`358`	`root.body.brect = Rect(Point(0, 0), size);`
`@@ -369,13 +370,13 @@ CNode& ContourScanner_::makeContour(schar& nbd_, const bool is_hole, const int x`
`369`	`370`
`370`	`371`	`const Point start_pt(x - (is_hole ? 1 : 0), y);`
`371`	`372`
`372`		`- CNode& res = tree.newElem();`
	`373`	`+ CNode& res = tree.newElem(Contour(storage));`
`373`	`374`	`res.body.isHole = is_hole;`
`374`	`375`	`res.body.isChain = isChain;`
`375`	`376`	`res.body.origin = start_pt + offset;`
`376`	`377`	`if (isSimple())`
`377`	`378`	`{`
`378`		`- icvFetchContourEx<schar>(this->arena, this->image, start_pt, MASK8_NEW, res.body, isDirect);`
	`379`	`+ icvFetchContourEx<schar>(this->image, start_pt, MASK8_NEW, res.body, isDirect);`
`379`	`380`	`}`
`380`	`381`	`else`
`381`	`382`	`{`
`@@ -384,7 +385,7 @@ CNode& ContourScanner_::makeContour(schar& nbd_, const bool is_hole, const int x`
`384`	`385`	`{`
`385`	`386`	`const int start_val = this->image.at<int>(start_pt);`
`386`	`387`	`lval = start_val & MASK8_LVAL;`
`387`		`- icvFetchContourEx<int>(this->arena, this->image, start_pt, 0, res.body, isDirect);`
	`388`	`+ icvFetchContourEx<int>(this->image, start_pt, 0, res.body, isDirect);`
`388`	`389`	`}`
`389`	`390`	`else`
`390`	`391`	`{`
`@@ -393,19 +394,19 @@ CNode& ContourScanner_::makeContour(schar& nbd_, const bool is_hole, const int x`
`393`	`394`	`nbd_ = (nbd_ + 1) & MASK8_LVAL;`
`394`	`395`	`if (nbd_ == 0)`
`395`	`396`	`nbd_ = MASK8_BLACK \| MASK8_NEW;`
`396`		`- icvFetchContourEx<schar>(this->arena, this->image, start_pt, lval, res.body, isDirect);`
	`397`	`+ icvFetchContourEx<schar>(this->image, start_pt, lval, res.body, isDirect);`
`397`	`398`	`}`
`398`	`399`	`res.body.brect.x -= this->offset.x;`
`399`	`400`	`res.body.brect.y -= this->offset.y;`
`400`	`401`	`res.ctable_next = this->ctable[lval];`
`401`	`402`	`this->ctable[lval] = res.self();`
`402`	`403`	`}`
`403`		`- const Point prev_origin = res.body.origin;`
	`404`	`+ // const Point prev_origin = res.body.origin;`
`404`	`405`	`res.body.origin = start_pt;`
`405`	`406`	`if (this->approx_method1 != this->approx_method2)`
`406`	`407`	`{`
`407`	`408`	`CV_Assert(res.body.isChain);`
`408`		`- approximateChainTC89(arena, res.body.codes, prev_origin, this->approx_method2, res.body.pts);`
	`409`	`+ // approximateChainTC89(arena, res.body.codes, prev_origin, this->approx_method2, res.body.pts);`
`409`	`410`	`res.body.isChain = false;`
`410`	`411`	`}`
`411`	`412`	`return res;`