From 6d1cdcf6011d69aad81add2fb4d47b3520ae659b Mon Sep 17 00:00:00 2001
From: gylns <gylpm@163.com>
Date: Fri, 14 Jul 2017 11:58:56 -0500
Subject: [PATCH] Merge pull request #8910 from gylns:mser

fix the MSER history's size issue (#8910)

* simplify growHistory and merge

* add assertion for history's size

* MSER: fix merging components' history
---
 modules/features2d/src/mser.cpp | 141 +++++++++++++++++++---------------------
 1 file changed, 67 insertions(+), 74 deletions(-)

diff --git a/modules/features2d/src/mser.cpp b/modules/features2d/src/mser.cpp
index 89083d0..9f4a4ca 100755
--- a/modules/features2d/src/mser.cpp
+++ b/modules/features2d/src/mser.cpp
@@ -262,98 +262,95 @@ public:
         }
 
         // add history chunk to a connected component
-        void growHistory( CompHistory*& hptr, WParams& wp, int new_gray_level, bool final, bool force=false )
+        void growHistory(CompHistory*& hptr, WParams& wp, int new_gray_level, bool final)
         {
-            bool update = final;
-            if( new_gray_level < 0 )
+            if (new_gray_level < gray_level)
                 new_gray_level = gray_level;
-            if( !history || (history->size != size && size > 0 &&
-                (gray_level != history->val || force)))
-            {
-                CompHistory* h;
-
-                if (history && gray_level == history->val)
-                    h = history;
-                else
-                {
-                    h = hptr++;
-                    h->parent_ = 0;
-                    h->child_ = history;
-                    h->next_ = 0;
-                    if (history)
-                        history->parent_ = h;
-                }
 
-                h->val = gray_level;
-                h->size = size;
-                h->head = head;
+            CompHistory *h;
+            if (history && history->val == gray_level)
+            {
+                h = history;
+            }
+            else
+            {
+                h = hptr++;
+                h->parent_ = 0;
+                h->child_ = history;
+                h->next_ = 0;
 
-                history = h;
-                h->var = FLT_MAX;
-                h->checked = true;
-                if (h->size >= wp.p.minArea)
+                if (history)
                 {
-                    h->var = -1.f;
-                    h->checked = false;
-                    update = true;
+                    history->parent_ = h;
                 }
             }
+            h->val = gray_level;
+            h->size = size;
+            h->head = head;
+            h->var = FLT_MAX;
+            h->checked = true;
+            if (h->size >= wp.p.minArea)
+            {
+                h->var = -1.f;
+                h->checked = false;
+            }
+
             gray_level = new_gray_level;
-            if( update && history && gray_level != history->val )
+            history = h;
+            if (history && history->val != gray_level)
+            {
                 history->updateTree(wp, 0, 0, final);
+            }
         }
 
         // merging two connected components
         void merge( ConnectedComp* comp1, ConnectedComp* comp2,
                     CompHistory*& hptr, WParams& wp )
         {
-            if( comp1->size < comp2->size )
+            if (comp1->gray_level < comp2->gray_level)
                 std::swap(comp1, comp2);
 
-            if( comp2->size == 0 )
+            gray_level = comp1->gray_level;
+            comp1->growHistory(hptr, wp, gray_level, false);
+            comp2->growHistory(hptr, wp, gray_level, false);
+
+            if (comp1->size == 0)
+            {
+                head = comp2->head;
+                tail = comp2->tail;
+            }
+            else
             {
-                // only grow comp1's history
-                comp1->growHistory(hptr, wp, -1, false);
-                gray_level = comp1->gray_level;
                 head = comp1->head;
-                tail = comp1->tail;
-                size = comp1->size;
-                history = comp1->history;
-                return;
+                wp.pix0[comp1->tail].setNext(comp2->head);
+                tail = comp2->tail;
             }
 
-            comp1->growHistory( hptr, wp, -1, false );
-            comp2->growHistory( hptr, wp, -1, false );
-
-            if (comp1->gray_level < comp2->gray_level)
-                std::swap(comp1, comp2);
-
-            gray_level = comp1->gray_level;
-            history = comp1->history;
-            wp.pix0[comp1->tail].setNext(comp2->head);
-
-            head = comp1->head;
-            tail = comp2->tail;
             size = comp1->size + comp2->size;
-            // update the history size
-            history->size =size;
+            history = comp1->history;
 
             CompHistory *h1 = history->child_;
             CompHistory *h2 = comp2->history;
-            if (h2->size > wp.p.minArea)
+            // the child_'s size should be the large one
+            if (h1 && h1->size > h2->size)
             {
-                // the child_'s size should be the large one
-                if (h1 && h1->size > h2->size)
+                // add h2 as a child only if its size is large enough
+                if(h2->size >= wp.p.minArea)
                 {
                     h2->next_ = h1->next_;
                     h1->next_ = h2;
+                    h2->parent_ = history;
                 }
-                else
+            }
+            else
+            {
+                history->child_ = h2;
+                h2->parent_ = history;
+                // reserve h1 as a child only if its size is large enough
+                if (h1 && h1->size >= wp.p.minArea)
                 {
-                    history->child_ = h2;
                     h2->next_ = h1;
                 }
-                h2->parent_ = history;
             }
         }
 
@@ -517,30 +514,26 @@ public:
                 ptr = *heap[curr_gray];
                 heap[curr_gray]--;
 
-                if( curr_gray < comptr[-1].gray_level )
+                if (curr_gray < comptr[-1].gray_level)
+                {
                     comptr->growHistory(histptr, wp, curr_gray, false);
+                    CV_DbgAssert(comptr->size == comptr->history->size);
+                }
                 else
                 {
-                    // keep merging top two comp in stack until the gray level >= pixel_val
-                    for(;;)
-                    {
-                        comptr--;
-                        comptr->merge(comptr, comptr+1, histptr, wp);
-                        if( curr_gray <= comptr[0].gray_level )
-                            break;
-                        if( curr_gray < comptr[-1].gray_level )
-                        {
-                            comptr->growHistory(histptr, wp, curr_gray, false);
-                            break;
-                        }
-                    }
+                    // there must one pixel with the second component's gray level in the heap,
+                    // so curr_gray is not large than the second component's gray level
+                    comptr--;
+                    CV_DbgAssert(curr_gray == comptr->gray_level);
+                    comptr->merge(comptr, comptr + 1, histptr, wp);
+                    CV_DbgAssert(curr_gray == comptr->gray_level);
                 }
             }
         }
 
         for( ; comptr->gray_level != 256; comptr-- )
         {
-            comptr->growHistory(histptr, wp, 256, true, true);
+            comptr->growHistory(histptr, wp, 256, true);
         }
     }
 
-- 
2.7.4