解决 自动完成难题的算法

龙4ik

成员
已加入
2020年10月24日
留言内容
16
编程经验
Beginner
我的任务是编写一个程序,将图像切成相等的矩形拼图。然后,程序必须解决这个难题,而又不知道它被切成薄片的方式。我写了代码,但是它一次又一次地工作,我可以't understand what problem is. Thank you in advance for any help.
附言该算法将每个片段放置在左上角,并尝试通过边界像素之间的最小差异找到最佳的邻近片段

自动完成难题:
using System;
using System.Collections.Generic;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Media.Imaging;

namespace Puzzles
{

    struct PixelColor
    {
        public byte Blue;
        public byte Green;
        public byte Red;
        public byte Alpha;
    }

    class Alghoritm
    {
        

        private List<int> GetNumbers(List<BitmapSource> list)
        {
            List<int> numbers = new List<int>();

            for (int i = 1; i <= list.Count; i++)
            {
                if (list.Count % i == 0)
                {
                    numbers.Add(i);
                }
            }

            return numbers;
        }
        private PixelColor[,] GetPixels(BitmapSource source)
        {
            if (source.Format != PixelFormats.Bgra32)
                source = new FormatConvertedBitmap(source, PixelFormats.Bgra32, null, 0);

            int width = source.PixelWidth;
            int height = source.PixelHeight;
            PixelColor[,] result = new PixelColor[width, height];


            source.CopyPixels(result, width * 4, 0, true);

            return result;
        }

        private double GetDifference(PixelColor first, PixelColor second)
        {
            int dr = Math.Abs(first.Red - second.Red);
            int dg = Math.Abs(first.Green - second.Green);
            int db = Math.Abs(first.Blue - second.Blue);
            int da = Math.Abs(first.Alpha - second.Alpha);

            return Math.Sqrt(dr * dr + dg * dg + db * db );
        }

        private double GetRightDifference(PixelColor[,] left, PixelColor[,] right)
        {
            double rightDifference = 0;

            try
            {
                if (left.Length != right.Length)
                    throw new Exception("Щось пішло не так");

                for (int i = 0; i < left.GetLength(0); i++)
                {
                    rightDifference += GetDifference(left[i, left.GetLength(1) - 1], right[i, 0]);
                }

            }
            catch (Exception ex)
            {
                MessageBox.Show(ex.Message);
            }

            return rightDifference;

        }

        private double GetBottomDifference(PixelColor[,] up, PixelColor[,] down)
        {
            double bottomDifference = 0;

            try
            {
                if (up.Length != down.Length)
                    throw new Exception("Щось пішло не так і тут");

                for (int i = 0; i < up.GetLength(1); i++)
                {
                    bottomDifference += GetDifference(up[up.GetLength(0) - 1, i], down[0, i]);
                }
            }
            catch (Exception ex)
            {
                MessageBox.Show(ex.Message);
            }

            return bottomDifference;
        }

        private BitmapSource GetRightImage(BitmapSource first, List<BitmapSource> list, ref double totalDifference)
        {
            double min = Int32.MaxValue;

            PixelColor[,] left = GetPixels(first);
            BitmapSource next = null;


            for (int i = 0; i < list.Count; i++)
            {
                PixelColor[,] right = GetPixels(list[i]);

                double value = GetRightDifference(left, right);

                if (min > value)
                {
                    next = list[i];
                    min = value;
                }
            }
            totalDifference += min;

            return next;
        }

        private BitmapSource GetBottomImage(BitmapSource first, List<BitmapSource> list, ref double totalDifference)
        {
            double min = Int32.MaxValue;

            PixelColor[,] up = GetPixels(first);
            BitmapSource next = null;


            for (int i = 0; i < list.Count; i++)
            {
                PixelColor[,] down = GetPixels(list[i]);

                double value = GetBottomDifference(up, down);

                if (min > value)
                {
                    next = list[i];
                    min = value;
                }
            }

            totalDifference += min;

            return next;
        }

        private double GetBestCurrentVariant(List<BitmapSource> list, int row,int col, ref BitmapSource[,] bestChoice)
        {
            BitmapSource bestPiece;

            double min = Int32.MaxValue;

                for (int j = 0; j < list.Count; j++)    //перебір всіх елементів колекції для даної розстановки
                {
                    double total = 0; //показує повну різницю всього малюнку

                    BitmapSource[,] elements = new BitmapSource[row, col];  //отриманий результат

                    List<BitmapSource> cash = new List<BitmapSource>(list);     //колекція доступних елементів

                    elements[0, 0] = cash[j];

                    cash.RemoveAt(j);

                    for (int irow = 0; irow < row - 1; irow++)    // перебір по рядкам
                    {
                        for (int icol = 0; icol < col - 1; icol++)  //перебір по стовпцям
                        {
                            //for(int icas = 0; icas<cash.Count;icas++)   //перебір по доступним елементам
                            //{
                            //}

                            bestPiece = GetRightImage(elements[irow, icol], cash, ref total);//отримуємо найкращий правий фрагмент
                            elements[irow, icol + 1] = bestPiece;//додаємо отриманий фрагмент до результату

                            cash.Remove(bestPiece);//видаляємо недоступний елемент

                        }

                        bestPiece = GetBottomImage(elements[irow, 0], cash, ref total);//отримуємо найкращий нижній фрагмент

                        elements[irow+1, 0] = bestPiece;//додаємо отриманий фрагмент до результату

                        cash.Remove(bestPiece);//видаляємо недоступний елемент
                    }

                    //додаємо фрагменти до останнього рядка
                    for (int icol = 0; icol < col - 1; icol++)  //перебір по стовпцям
                    {
                        bestPiece = GetRightImage(elements[row - 1, icol], cash, ref total);//отримуємо найкращий правий фрагмент
                        elements[row - 1, icol + 1] = bestPiece;//додаємо отриманий фрагмент до результату

                        cash.Remove(bestPiece);//видаляємо недоступний елемент
                    }

                    if (min > total)
                    {
                        bestChoice = (BitmapSource[,])elements.Clone();
                        min = total;
                    }
                }

            return min;
        }

        public BitmapSource[,] GetBestPuzzleImage(List<BitmapImage> list)
        {
            List<BitmapSource> bmp = new List<BitmapSource>();

            for(int i=0;i<list.Count;i++)
            {
                BitmapSource temp = (BitmapSource)list[i];
                bmp.Add(temp);
            }

            List<int> numbers = new List<int>(GetNumbers(bmp));

            BitmapSource[,] bestChoice = null;

            double min = Int32.MaxValue;  //значення найменшої різниці малюнку(для визначення найкращого результату)

            for (int i = 0; i < numbers.Count;i++)
            {
                int row = numbers[i];   //кількість рядків
                int col = list.Count / row;     //кількість стовпців

                BitmapSource[,] possibleChoice = new BitmapSource[row,col];

                double value = GetBestCurrentVariant(bmp, row, col, ref possibleChoice);

                if (min > value)
                {
                    bestChoice = (BitmapSource[,])possibleChoice.Clone();

                    min = value;
                }
            }

            return bestChoice;
        }
    }
}
 

跳伞

工作人员
已加入
2019年4月6日
留言内容
2,605
地点
弗吉尼亚州切萨皮克
编程经验
10+
您能否解释一下代码遇到的问题以及已经尝试解决的问题?
 

金西尼

C#论坛主持人
工作人员
已加入
2011年4月23日
留言内容
3,563
地点
悉尼,澳大利亚
编程经验
10+
您需要调试代码,逐行逐步执行,并根据算法确定您期望在每个步骤中执行的操作。当发现发生的事情与您的期望不符时,您发现了一个问题。即使您仍然无法解决该问题,至少也可以向我们提供所有相关信息。
 

龙4ik

成员
已加入
2020年10月24日
留言内容
16
编程经验
Beginner
是原始图片
2.jpg

什么会返回alghoritm:
1603613827633.png


或者
1603613924793.png


我通过调试器查看了算法,但无法理解,为什么它选择此变体为最佳选择,并将其视为边界像素之间的总差异最小的变体。当它与完成拼图的RIGHT变体一起使用时,会发现,该变体没有最小的差异。

附言我还添加了切片算法的代码(我希望它也可能是问题的根源,并且还可能认为它不能以正确的方式对图像进行切片):
Slicing alghoritm:
for (int y = 0, i=0; y < image.ActualHeight; y+=nheight, i++)
            {
                for (int x = 0, j=0; x < image.ActualWidth; x+=nwidth, j++)
                {
                    var encoder = new PngBitmapEncoder();

                    //розріз зораження на окремі фрагменти
                    try
                    {
                        CroppedBitmap cb = new CroppedBitmap((BitmapSource)bitmap, new Int32Rect(x, y, nwidth, nheight));
                        Image img = new Image { Source = cb };
                      
                        encoder.Frames.Add(BitmapFrame.Create((BitmapSource)img.Source));
                    }
                    catch(ArgumentException ex)
                    {
                        break;
                    }
                    
                    //шлях для окремого фрагменту
                    string filename = path + "\\"+ source + $"_{i}_{j}.jpg";
                    
                    //збереження фрагменту
                    try
                    {
                        using (FileStream stream = new FileStream(filename, FileMode.Create))
                        {
                            encoder.Save(stream);
                        }
                    }
                    catch(Exception ex)
                    {
                        MessageBox.Show("Вказаний невірний шлях");
                    }
                }
            }
 

金西尼

C#论坛主持人
工作人员
已加入
2011年4月23日
留言内容
3,563
地点
悉尼,澳大利亚
编程经验
10+
我用调试器浏览了alghoritm
你真的?因此,您在代码的顶部设置了一个断点,然后逐行浏览该代码,并观察了每一步代码是否都按预期执行了?在这种情况下,必须发生以下两种情况之一。一种可能是该代码完全按照您的预期执行了每个步骤。在这种情况下,您的期望是错误的,您的期望需要重新评估。另一个可能性是,实际发生的事情与您的期望有所不同。在这种情况下,您可以告诉我们确切的位置和确切的方式。哪有
 

龙4ik

成员
已加入
2020年10月24日
留言内容
16
编程经验
Beginner
你真的?因此,您在代码的顶部设置了一个断点,然后逐行浏览该代码,并观察了每一步代码是否都按预期执行了?在这种情况下,必须发生以下两种情况之一。一种可能是该代码完全按照您的预期执行了每个步骤。在这种情况下,您的期望是错误的,您的期望需要重新评估。另一个可能性是,实际发生的事情与您的期望有所不同。在这种情况下,您可以告诉我们确切的位置和确切的方式。哪有
它发生在以下代码块中:

C#:
public static void CopyPixels(this BitmapSource source, PixelColor[,] pixels, int stride, int offset, bool dummy)
        {
            var height = source.PixelHeight;
            var width = source.PixelWidth;
            var pixelBytes = new byte[height * width * 4];
            source.CopyPixels(pixelBytes, stride, 0);
            int y0 = offset / width;
            int x0 = offset - width * y0;
            for (int y = 0; y < height; y++)
                for (int x = 0; x < width; x++)
                    pixels[x + x0, y + y0] = new PixelColor
                    {
                        Blue = pixelBytes[(y * width + x) * 4 + 0],
                        Green = pixelBytes[(y * width + x) * 4 + 1],
                        Red = pixelBytes[(y * width + x) * 4 + 2],
                        Alpha = pixelBytes[(y * width + x) * 4 + 3],
                    };
        }
它返回裁剪图像像素的数组,然后将此结果发送给函数 GetDifference():

C#:
private double GetDifference(PixelColor first, PixelColor second)
        {
            int dr = Math.Abs(first.Red - second.Red);
            int dg = Math.Abs(first.Green - second.Green);
            int db = Math.Abs(first.Blue - second.Blue);
            int da = Math.Abs(first.Alpha - second.Alpha);

            return Math.Sqrt(dr * dr + dg * dg + db * db );
        }

当计算差异时,可以看到RIGHT变体将具有"更差" 每次像素,比其他。而且我不知道为什么会这样:也许它不能以正确的方式获得像素,或者切片算法会使相邻片段之间的间隙过大,从而导致计算错误。

我知道我的答案仍然不完整,但是我希望这些信息能为您提供足够的信息。感谢您的关注!
 
最佳 底部