算法:反转图像(旋转的矩阵)

简介: 旋转的矩阵

前言

今天要介绍的是一个较为经典的算法题:反转图像或者旋转矩阵。这道题的原题是Leetcode上的一道题,在题库序号为48。具体内容粘贴如下:
屏幕截图 2022-12-23 105925.png
这种题目就是一个典型的倒置矩阵的思路,大体内容就是将一个矩阵逆向反转90度。首先针对这题有两种解法,一种就是显而易见的暴力转置法,就是将矩阵的对角线为分界线将两边的数字进行交换,之后再将矩阵的每行前半部分和后半部分进行对换,这时候矩阵的倒置90度就完成了。第二种就是通过分治思想,将矩阵分割成四块,一块进行逆转90度的同时就可以将其他的联通一起逆转,实现通过一部分操作从而带动整体。

第一种解法

这种解法首先是以矩阵的对角线划分,将两边的数字进行互换
屏幕截图 2022-12-28 193005.png
屏幕截图 2022-12-28 193327.png
上述红线就是一条对焦分界线,通过交换分解线两边的数字,将边角进行交换,实现第一个旋转步骤。交换后的结果如图所示:
屏幕截图 2022-12-28 193633.png

第二步将每行的前后进行互换,但是行中心不变,因为已经旋转过了,中心块位置固定所以只需一次变换即可,两边的棱角就需要进行两次操作。
屏幕截图 2022-12-30 121517.png
屏幕截图 2022-12-30 121729.png
这样经过两步的操作,这个矩阵就彻底的被倒置了90度,操作难度并不是很大,但是有些麻烦。但是这是平常最容易想到的解法,通过先交换中心块和边角,再通过行前后半部分进行交换即可成功解决。以下附上Java代码演示全部过程:

/**
     * 首先矩阵倒置,再翻转每一行的两边
     * @param matrix
     */
    public void rotate(int[][] matrix){

        int len=matrix.length;

        //倒置矩阵第一步,除去左上到右下的中分线和中心点,其他位置与对侧交换
        for (int i = 0; i <matrix.length; i++) {
            for (int j = i+1; j <matrix[i].length; j++) {
                if (i==j){
                    continue;
                }

                int temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }


        //每行的首尾位置进行交换,矩阵倒置的最·后一步
        for (int i = 0; i <matrix.length; i++) {
            for (int j = 0; j <len/2; j++) {
                int temp=matrix[i][j];
                matrix[i][j]=matrix[i][len-j-1];
                matrix[i][len-j-1]=temp;
            }

        }
    }

第二种解法

这是一个比较经典的通过分治的思想进行解决问题。先将矩阵分为四个小矩阵

屏幕截图 2022-12-30 174050.png
然后逐一将小矩阵的数字进行倒置90度,小矩形的块旋转变化符合一定的规律,行列转化的规律:row+newCol = n - 1,col = newRow。这里row、col表示数字的原有坐标,newRow、newCol表示旋转后的新坐标。遍历每个小矩阵中的数字进行倒置旋转
屏幕截图 2022-12-30 175726.png
屏幕截图 2022-12-30 182902.png
这种通过分治只需要导致旋转一个矩阵内的数字就可以将整个大矩阵进行旋转,注意:中心点数字不需要进行操作。使用Java代码演示:

 /**
     * 首先矩阵倒置,再翻转每一行的两边
     * @param matrix
     */
    public void rotate(int[][] matrix){

        int len=matrix.length;

        //遍历四分之一矩阵,左上角
        for (int i = 0; i < len/2 + len%2; i++) {
            for (int j = 0; j < len/2; j++) {
                //对于matrix[i][j],需要找到不同的四个矩阵中对应的另外三个位置和元素
                //定义一个临时的数组,保存对应的四个元素
                int[] temp=new int[4];
                int row = i;
                int col = j;

                //行列转化的规律:row+newCol = n - 1,col = newRow
                //四个旋转块中的一个元素四次旋转落地存入临时数组中
                for (int k = 0; k < 4 ; k++) {
                    temp[k] = matrix[row][col];;
                    int x = row;
                    row = col;
                    col = len - 1 - x;

                }


                for (int k = 0; k < 4; k++) {
                    //将下个位置的数依次前移填入相应的位置
                    matrix[row][col] = temp[(k+3)%4];
                    int x = row;
                    row = col;
                    col = len - 1 -x;
                }

            }

        }
    }

总结

对比上述两种可以得出,第二种无论是在设计精巧还是代码量方面都比第二种要更好,推荐使用第二种方式的分治思想进行解决问题。

相关文章
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
阿里云人工智能平台 PAI 团队发表的图像编辑算法论文在 MM2024 上正式亮相发表。ACM MM(ACM国际多媒体会议)是国际多媒体领域的顶级会议,旨在为研究人员、工程师和行业专家提供一个交流平台,以展示在多媒体领域的最新研究成果、技术进展和应用案例。其主题涵盖了图像处理、视频分析、音频处理、社交媒体和多媒体系统等广泛领域。此次入选标志着阿里云人工智能平台 PAI 在图像编辑算法方面的研究获得了学术界的充分认可。
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
|
26天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
1月前
|
机器学习/深度学习 算法 搜索推荐
django调用矩阵分解推荐算法模型做推荐系统
django调用矩阵分解推荐算法模型做推荐系统
28 4
|
1月前
|
机器学习/深度学习 人工智能 算法
【MM2024】面向 StableDiffusion 的多目标图像编辑算法 VICTORIA
阿里云人工智能平台 PAI 团队与华南理工大学合作在国际多媒体顶级会议 ACM MM2024 上发表 VICTORIA 算法,这是一种面向 StableDiffusion 的多目标图像编辑算法。VICTORIA 通过文本依存关系来修正图像编辑过程中的交叉注意力图,从而确保关系对象的一致性,支持用户通过修改描述性提示一次性编辑多个目标。
|
1月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
101 0
|
1月前
|
算法 数据安全/隐私保护
织物图像的配准和拼接算法的MATLAB仿真,对比SIFT,SURF以及KAZE
本项目展示了织物瑕疵检测中的图像拼接技术,使用SIFT、SURF和KAZE三种算法。通过MATLAB2022a实现图像匹配、配准和拼接,最终检测并分类织物瑕疵。SIFT算法在不同尺度和旋转下保持不变性;SURF算法提高速度并保持鲁棒性;KAZE算法使用非线性扩散滤波器构建尺度空间,提供更先进的特征描述。展示视频无水印,代码含注释及操作步骤。
|
2月前
|
算法 数据可视化 数据安全/隐私保护
基于LK光流提取算法的图像序列晃动程度计算matlab仿真
该算法基于Lucas-Kanade光流方法,用于计算图像序列的晃动程度。通过计算相邻帧间的光流场并定义晃动程度指标(如RMS),可量化图像晃动。此版本适用于Matlab 2022a,提供详细中文注释与操作视频。完整代码无水印。
|
4月前
|
机器学习/深度学习 编解码 监控
算法金 | 深度学习图像增强方法总结
**图像增强技术概括** 图像增强聚焦于提升视觉效果和细节,广泛应用于医学、遥感等领域。空间域增强包括直方图均衡化(增强对比度)、对比度拉伸、灰度变换、平滑滤波(均值、中值)和锐化滤波(拉普拉斯、高通)。频率域增强利用傅里叶变换、小波变换,通过高频和低频滤波增强图像特征。现代方法涉及超分辨率重建、深度学习去噪(如CNN、Autoencoder)、图像修复(如GAN)和GANs驱动的多种图像处理任务。
148 14
算法金 | 深度学习图像增强方法总结
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
3月前
|
算法 前端开发 计算机视觉
基于均值坐标(Mean-Value Coordinates)的图像融合算法的优化实现
基于均值坐标(Mean-Value Coordinates)的图像融合算法的优化实现
43 0