How to speed up Connected Component Labeling (second pass)

Question

I need advice how to speed up the second pass of CCL algorithm. First pass takes only a few milliseconds, but second pass takes a few seconds. I tried several times to optimize the table of equivalences or use pointers, but second pass is always very slow. Thanks for any advice

       Bitmap bmp = null;

        unsafe
        {
            int stride = _alg.MIplImage.widthStep;
            byte* ptr = (byte*)_alg.MIplImage.imageData;
            byte[] prevRow = new byte[_alg.Cols];

            //First pass
            for (int i = 1; i < _alg.Rows; i++)
            {
                for (int j = 1; j < _alg.Cols; j++)
                {
                    //White pixels only
                    if ((byte)ptr[j] == 255)
                    {
                        //8-connected
                        byte[] array = new byte[4] { ptr[j - 1], prevRow[j - 1], prevRow[j], prevRow[j + 1] };
                        //New Label
                        if (array.All(x => x == 0))
                        {
                            ptr[j] = _color;
                            prevRow[j] = ptr[j];
                            _color++;
                            continue;
                        }

                        byte max = array.Max();
                        byte min = array.Where(f => f > 0).Min();

                        //color dispute
                        if (max != min)
                        {
                            ptr[j] = min;

                            if (_prevMax != max)
                            {   
                                _fromToD.Add(max, min);   //Add to equvalence table
                                _prevMax = max;
                            }

                        }
                        else if (max == min)   //Same color
                        {
                            ptr[j] = min;
                        }
                    }

                    prevRow[j] = ptr[j];   //Aktualize previous row

                }

                ptr += stride;
            }

            //To this section, about 16 ms
            //second pass

            //byte* p = (byte*)(void*)bmData.Scan0.ToPointer();
            //int stopAddress = (int)p + bmData.Stride * bmData.Height;

            //while ((int)p != stopAddress)
            //{
            //    foreach (KeyValuePair<byte, byte> pair in _fromToD)
            //    {
            //        if (p[0] == pair.Key)
            //        {
            //            p[0] = pair.Value;
            //        }
            //    }
            //    p++;
            //}

            //bmp.UnlockBits(bmData);
            //About 3 sec

Answer 1

Pointer from other end finally helped. The algorithm is already in milliseconds, not seconds. It's not the fastest implementation but maybe it helps someone.

private unsafe Bitmap ApplyAlgoritmPointer()
    {
        _alg._Erode(1);      //EmguCV Image.Erode
        _alg._Dilate(3);

        Bitmap b = _alg.Bitmap;
        BitmapData bData = b.LockBits(new Rectangle(0, 0, _alg.Width, _alg.Height), ImageLockMode.ReadWrite, PixelFormat.Format8bppIndexed);

        byte* scan0 = (byte*)bData.Scan0.ToPointer();

        for (int i = 1; i < bData.Height - 1; i++)
        {
            for (int j = 1; j < bData.Width - 1; j++)
            {
                byte* dataCurrent = scan0 + i * bData.Stride + j;

                //White pixels only
                if (dataCurrent[0] == 255)
                {
                    byte* dataLeft = scan0 + i * bData.Stride + (j - 1);
                    byte* dataTopLeft = scan0 + (i - 1) * bData.Stride + (j - 1);
                    byte* dataTop = scan0 + (i - 1) * bData.Stride + j;
                    byte* dataTopRight = scan0 + (i - 1) * bData.Stride + (j + 1);

                    //New label
                    if (dataLeft[0] == 0 && dataTopRight[0] == 0 && dataTopLeft[0] == 0 && dataTop[0] == 0)
                    {
                        dataCurrent[0] = _color;
                        _pixels.Add(new pixel(dataCurrent, _color));
                        _color++;
                    }
                    else
                    {
                        byte*[] array = new byte*[4] { dataLeft, dataTopLeft, dataTop, dataTopRight };
                        byte* max = array.MaxP();
                        byte* min = array.MinP();

                        if (max != min)   //Differend colors
                        {
                            dataCurrent[0] = min[0];                                 //menim obsah adresy

                            if (!_fromToD.ContainsKey(max[0]))
                            {
                                if (max[0] == 255) continue;

                                _fromToD.Add(max[0], new List<byte>() { min[0] });
                            }
                            else
                            {
                                if (!_fromToD[max[0]].Contains(min[0]))
                                {
                                    _fromToD[max[0]].Add(min[0]);
                                }
                            }

                            _pixels.Add(new pixel(dataCurrent, min[0]));
                        }
                        else if (max == min)   //Same color
                        {
                            dataCurrent[0] = min[0];
                            _pixels.Add(new pixel(dataCurrent, min[0]));
                        }
                    }

                }
            }
        }

        //Second Pass
        NewList();

        for (int k = 0; k < _pixels.Count; k++)
        {
            for (int l = 0; l < _fromTo.Count; l++)
            {
                if (_pixels[k].color == _fromTo[l].from)
                {
                    _pixels[k].pix[0] = _fromTo[l].to;
                }
                else continue;
            }
        }

        b.UnlockBits(bData);

        return b;

    }

Tables equivalence reduction

    private void NewList()
    {
        foreach (var key in _fromToD.Reverse())
        {
            _fromTo.Add(new pass(key.Key, GetByteRecursive(key.Key)));
        }
    }

    private byte GetByteRecursive(byte p)
    {
        byte next = p;

        if (_fromToD.ContainsKey(p))
        {
            next = _fromToD[p].Last();
            return GetByteRecursive(next);
        }
        else
        {
            return next;
        }
    }

    class pass
    {
        public byte from;
        public byte to;

        public pass(byte from, byte to)
        {
            this.from = from;
            this.to = to;
        }
    }

    unsafe class pixel
    {
        public byte* pix;
        public byte color;

        public pixel(byte* pixel, byte color)
        {
            this.pix = pixel;
            this.color = color;
        }
    }