【数学建模】碎纸片的拼接复原

news/2024/7/19 21:11:34/文章来源:https://blog.csdn.net/weixin_72899100/article/details/139226638

2013高教社杯全国大学生数学建模竞赛B题

  • 问题一
    • 模型一
    • 模型二
      • 条件设立思路
    • 问题求解

问题一

已知 d i d_i di为第 i i i张图片图片的像素矩阵
已知 d i d_i di都是 n ∗ m n*m nm二维矩阵
假设有 N N N张图片

模型一

我们认为对应位置像素匹配为
d i [ j ] [ 1 ] = d k [ j ] [ m ] d_i[j][1]=d_k[j][m] di[j][1]=dk[j][m]
那么就有
图片之间匹配度数组
A [ i ] [ k ] = ∑ j = 1 m d i [ j ] [ 1 ] = d k [ j ] [ m ] A[i][k] = \displaystyle\sum_{j=1}^m d_i[j][1]=d_k[j][m] A[i][k]=j=1mdi[j][1]=dk[j][m]
其中 A [ i ] [ k ] A[i][k] A[i][k]表示第 i i i张图片放在第 k k k图片后面的匹配度
建立模型:
目标是总匹配度最大
设立0/1变量 x i j = 1 x_{ij}=1 xij=1表示选择第 i i i张在第 j j j张后面,并且 A [ i ] [ j ] A[i][j] A[i][j]表示为 A i j A_{ij} Aij
已知起始图片为 a a a,终止图片为 b b b
{ max ⁡ ∑ i = 1 N ∑ j = 1 N x i j A i j ∑ j = 1 N x i j = 1 , i = a , i = j ∑ i = 1 N x i j = 1 , j = b , j = i i = 1 , . . . , N , j = 1 , . . . , N \begin{cases} \max \displaystyle\sum_{i=1}^N \displaystyle\sum_{j=1}^N x_{ij}A_{ij}\\ \displaystyle\sum_{j=1}^N x_{ij} = 1 , i \cancel{=} a , i \cancel{=} j \\ \displaystyle\sum_{i=1}^N x_{ij} = 1 , j \cancel{=} b , j \cancel{=} i \\ i = 1,...,N , j = 1,...,N \end{cases} maxi=1Nj=1NxijAijj=1Nxij=1,i= a,i= ji=1Nxij=1,j= b,j= ii=1,...,N,j=1,...,N

模型二

我们认为对应位置像素匹配不成功的差异为
∣ d i [ j ] [ 1 ] − d k [ j ] [ m ] ∣ |d_i[j][1]-d_k[j][m]| di[j][1]dk[j][m]
那么就有
图片之间差异度数组
A [ i ] [ k ] = ∑ j = 1 m ∣ d i [ j ] [ 1 ] − d k [ j ] [ m ] ∣ A[i][k] = \displaystyle\sum_{j=1}^m |d_i[j][1]-d_k[j][m]| A[i][k]=j=1mdi[j][1]dk[j][m]
其中 A [ i ] [ k ] A[i][k] A[i][k]表示第 k k k张图片放在第 i i i图片后面的差异度
建立模型:
目标是总差异度最小

设立0/1变量 x i j = 1 x_{ij}=1 xij=1表示选择第 j j j张在第 i i i张后面,并且 A [ i ] [ j ] A[i][j] A[i][j]表示为 A i j A_{ij} Aij
已知起始图片为 a a a,终止图片为 b b b
得到目标 min ⁡ ∑ i = 1 N ∑ j = 1 N x i j A i j \min \displaystyle\sum_{i=1}^N \displaystyle\sum_{j=1}^N x_{ij}A_{ij} mini=1Nj=1NxijAij
要保证除开起始图片,每个图片都有前一张与其对应
∑ i = 1 N x i j = 1 , j = a \displaystyle\sum_{i=1}^N x_{ij} = 1 , j \cancel{=} a i=1Nxij=1,j= a
同时除开终止图片也是,要有后一张与其对应
∑ j = 1 N x i j = 1 , i = b \displaystyle\sum_{j=1}^N x_{ij} = 1 , i \cancel{=} b j=1Nxij=1,i= b

条件设立思路

将其看作类似最短路问题
已知起点 a a a,终点为 b b b,图中每个节点都与其他节点有边,求从起点到终点的最短路问题,并且需要经过每一个节点!

目标依旧不变。
min ⁡ ∑ i = 1 N ∑ j = 1 N x i j A i j \min \displaystyle\sum_{i=1}^N \displaystyle\sum_{j=1}^N x_{ij}A_{ij} mini=1Nj=1NxijAij
要保证除开起始图片,每个图片都有前一张与其对应,实际上是除开起点,每个节点的入度都为1
$\displaystyle\sum_{i=1}^N x_{ij} = 1 , j \cancel{=} a $
同理除开终点每个节点出度为1
∑ j = 1 N x i j = 1 , i = b \displaystyle\sum_{j=1}^N x_{ij} = 1 , i \cancel{=} b j=1Nxij=1,i= b
避开自环存在
x i i = 0 , i = 1 , . . , N x_{ii} = 0 ,i=1,..,N xii=0,i=1,..,N
现在唯一的问题就是可能会出现,起点连几个点就到终点,其他点连成环。

目前解决办法,多次运行,如果出现上述情况,手动排除
假设 3 − > 4 − > 5 − > 6 − > 3 3->4->5->6->3 3>4>5>6>3成环了
那么 x 34 + x 45 + x 56 + x 63 = 4 x_{34}+x_{45}+x_{56}+x_{63}\cancel{=} 4 x34+x45+x56+x63= 4

所以模型如下:
A [ i ] [ k ] = ∑ j = 1 m ∣ d i [ j ] [ 1 ] − d k [ j ] [ m ] ∣ A[i][k] = \displaystyle\sum_{j=1}^m |d_i[j][1]-d_k[j][m]| A[i][k]=j=1mdi[j][1]dk[j][m]
{ min ⁡ ∑ i = 1 N ∑ j = 1 N x i j A i j ∑ i = 1 N x i j = 1 , j = a ∑ j = 1 N x i j = 1 , i = b i = 1 , . . . , N , j = 1 , . . . , N \begin{cases} \min \displaystyle\sum_{i=1}^N \displaystyle\sum_{j=1}^N x_{ij}A_{ij}\\ \displaystyle\sum_{i=1}^N x_{ij} = 1 , j \cancel{=} a \\ \displaystyle\sum_{j=1}^N x_{ij} = 1 , i \cancel{=} b \\ i = 1,...,N , j = 1,...,N \end{cases} mini=1Nj=1NxijAiji=1Nxij=1,j= aj=1Nxij=1,i= bi=1,...,N,j=1,...,N

问题求解

数据处理:
MATLAB

d =cell(1,19);
for i = 1:19imageName=strcat(num2str(i-1,'%03d'),'.bmp');d{i}=imread(imageName);
end
a = cell(19,19);
for i = 1:19for j = 1:19sum = 0;for jj = 1:1980sum = sum + abs( double(d{i}(jj,72))-double(d{j}(jj,1)) );% j在i后面的差值enda{i,j} = sum; % 顺序是 i jend
end
xlswrite('D:\homewrok\建模\纸片\201391394826489\2013年全国大学生数学建模竞赛B题附件\附件1\a.xls', a);

lingo

sets:aa/1..19/:;cc(aa,aa):x,d;
endsets
data:a = 9;b = 7;d = @ole('D:\homewrok\建模\纸片\201391394826489\2013年全国大学生数学建模竞赛B题附件\附件1\a.xls','A1:S19');
enddata
min = @sum(cc(i,j):x(i,j)*d(i,j));
@for(aa(i)|(i#ne#b):@sum(aa(j):x(i,j))=1);
@for(aa(j)|(j#ne#a):@sum(aa(i):x(i,j))=1);
@for(cc(i,j)|(i#eq#j):x(i,j)=0);
@for(cc(i,j):@bin(x(i,j)));@for(aa(j):x(b,j)=0);
@for(aa(i):x(i,a)=0);

第一次

                       X( 1, 7)        1.000000            25661.00X( 2, 5)        1.000000            33616.00X( 3, 17)        1.000000            14639.00X( 4, 11)        1.000000            31383.00X( 5, 6)        1.000000            22300.00X( 6, 10)        1.000000            24650.00X( 8, 18)        1.000000            33594.00X( 9, 15)        1.000000            27544.00X( 10, 14)        1.000000            26131.00X( 11, 3)        1.000000            22137.00X( 12, 8)        1.000000            21828.00X( 13, 16)        1.000000            12228.00X( 14, 19)        1.000000            21352.00X( 15, 13)        1.000000            18222.00X( 16, 4)        1.000000            24331.00X( 17, 2)        1.000000            29574.00X( 18, 1)        1.000000            26993.00X( 19, 12)        1.000000            27268.00

发现没有出现上面担心的问题
MATLAB

d =cell(1,19);
for i = 1:19imageName=strcat(num2str(i-1,'%03d'),'.bmp');d{i}=imread(imageName);
end
ansd = [d{9},d{15},d{13},d{16},d{4},d{11},d{3},d{17},d{2},d{5},d{6},d{10},d{14},d{19},d{12},d{8},d{18},d{1},d{7}];
imshow(ansd);

在这里插入图片描述

同理做附件二:

d =cell(1,19);
for i = 1:19imageName=strcat(num2str(i-1,'%03d'),'.bmp');d{i}=imread(imageName);
end
ansd = [d{4},d{7},d{3},d{8},d{16},d{19},d{12},d{1},d{6},d{2},d{10},d{14},d{11},d{9},d{13},d{15},d{18},d{17},d{5}];
imshow(ansd);

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1052805.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

clocking wizard IP核通过AXI4-Lite接口实现动态重新配置应用实例

在最近的FPGA应用中,应用到了基于Zynq 7000的Uart串口设计,为了让串口的时钟更精确,采用了外部时钟模式,如下图所示。外部时钟连接到了Clocking Wizard IP核的输出端。 在串口通信时,发现串口有错码出现。例如&#xf…

leetcode124 二叉树中的最大路径和-dp

题目 二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root &…

C++模板方法模式

文章目录 1. 定义抽象基类(Abstract Class)2. 实现具体子类(Concrete Class)3. 使用模板方法模板方法模式的优点模板方法模式的应用场景注意事项实现示例抽象类(模板)具体实现类客户端代码 总结 模板方法模…

Elasticsearch (ES) (上万字)详细学习总结

一、认识ES 二、ES相关安装和部署(elasticsearch 、kbana、ik) 这部分的内容可以查看我之前写的Docker常用部署这篇文章 三、Mapping映射 3.1 Mapping映射属性 3.2 索引库操作 3.2.1 遵循Restful规范说明 3.2.2 具体使用方式说明 3.2.3增删改查示例 #创建 PUT /heima {&q…

【Java面试】四、MySQL篇(上)

文章目录 1、定位慢查询2、慢查询的原因分析3、索引3.1 数据结构选用:二叉树 & 红黑树3.2 数据结构选用:B树 4、聚簇索引、非聚簇索引、回表查询4.1 聚簇索引、非聚簇索引4.2 回表查询 5、覆盖索引、超大分页优化5.1 覆盖索引5.2 超大分页处理 6、索…

存储+调优:存储-memcached

存储调优:存储-memcached 什么是memcached? 高性能的分布式内存缓存服务器。通过缓存数据库的查询结果,减少数据库访问次数,以提高动态Web应用的速度、提高可扩展性。 在memcached中存什么? 尽快被保存 访问频率高 1.数据保…

【Unity】Unity项目转抖音小游戏(三)资源分包,抖音云CDN

业务需求,开始接触一下抖音小游戏相关的内容,开发过程中记录一下流程。 使用资源分包可以优化游戏启动速度,是抖音小游戏推荐的一种方式,抖音云也提供存放资源的CDN服务 抖音云官方文档:https://developer.open-douyi…

R可视化:另类的箱线图

介绍 方格状态的箱线图 加载R包 knitr::opts_chunk$set(echo TRUE, message FALSE, warning FALSE) library(patternplot) library(png) library(ggplot2) library(gridExtra)rm(list ls()) options(stringsAsFactors F)导入数据 data <- read.csv(system.file(&qu…

雷达基数据绘制成雷达图

x波段雷达基数据绘制成雷达图 1.雷达基数据格式Z_RADR_I_ZR001_20240521020002_O_DOR_YLD2-D_CAP_FMT.bin.bz2 2.基数据读取 python f StandardData(i) # 新版本标准数据radarTime f.scantime # 获取雷达时次date_str radarTime.strftime(%Y-%m-%d %H:%M:%S)date_str d…

C#【进阶】排序进阶

排序进阶 文章目录 插入排序希尔排序归并排序快速排序堆排序 插入排序 #region 知识点一 插入排序的基本原理 // 8 7 1 5 4 2 6 3 9 // 两个区域 // 排序区 // 未排序区 // 用一个索引值做分水岭// 未排序区元素 // 与排序区元素比较 // 插入到合适位置 // 直到未排序区清空 #e…

Docker(三) 容器管理

1 容器管理概述 Docker 的容器管理可以通过 Docker CLI 命令行工具来完成。Docker 提供了丰富的命令&#xff0c;用于管理容器的创建、启动、停止、删除、暂停、恢复等操作。 以下是一些常用的 Docker 容器命令&#xff1a; 1、docker run&#xff1a;用于创建并启动一个容器。…

Qt教程3-Ubuntu(x86_64)上配置arm64(aarch64)交叉编译环境及QT编译arm64架构工程

汇创慧玩 写在前面1. 查看系统架构相关指令2. ARM64交叉编译器环境搭建3. Qt编译arm64环境搭建4. 配置 Qt的本地aarch64交叉编译器5. 工程建立及编译验证 写在前面 苦辣酸甜时光八载&#xff0c;春夏秋冬志此一生 Qt简介&#xff1a; Qt&#xff08;官方发音 [kju:t]&#xff…

Spring Boot集成六大常用中间件,附集成源码,亲测有效

目录 万字论文&#xff0c;从0到1&#xff0c;只需1小时获取途径1、Spring Boot如何集成Spring Data JPA&#xff1f;2、Spring Boot如何集成Spring Security&#xff1f;3、Spring Boot如何集成Redis&#xff1f;4、Spring Boot如何集成RabbitMQ&#xff1f;5、Spring Boot如何…

【C++】C++11(一)

C11是一次里程碑式的更新&#xff0c;我们一起来看一看~ 目录 列表初始化&#xff1a;{ }初始化&#xff1a;std::initializer_list&#xff1a; 声明&#xff1a;auto&#xff1a;decltype&#xff1a; STL的一些变化&#xff1a; 列表初始化&#xff1a; { }初始化&#xf…

云计算期末复习(2)

MapReduce 包含Google MapReduce基本构架、Hadoop MapReduce基本构架 作业&#xff08;问答题&#xff09; &#xff08;1&#xff09;预习论文The Google File System&#xff0c;总结和分析GFS主要特点。 GFS的主要特点包括&#xff1a; 1. 高可靠性和容错性&#xff1a;G…

政府鼓励社会力量建设气膜体育场馆—轻空间

2023年12月1日&#xff0c;国家体育安全总局发布的《关于政协第十四届全国委员会第一次会议第00374号&#xff08;文体宣传类020号&#xff09;提案答复的函》中指出&#xff0c;2016年和2020年国务院发布的文件中均涉及推动气膜场馆建设及完善装配式建筑相关政策。下一步&…

炸裂!AI五分钟模仿爆款IP故事,涨粉速度太绝了!

‍ ‍大家好&#xff0c;我是向阳。 今天我要分享一个利用AI技术模仿爆款账号的小技巧&#xff0c;帮助大家迅速增加粉丝。这个方法简单实用&#xff0c;尤其适用于副业和本地生活领域。接下来&#xff0c;我将为大家详细讲解操作步骤。让我们开始吧。 副业赚钱&#xff1a;模…

2024年03月 Python(四级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,共50分) 第1题 运行如下代码,若输入整数3,则最终输出的结果为?( ) def f(x):if x==1:s=1else:s

基于 IP 的 DDOS 攻击实验

介绍 基于IP的分布式拒绝服务&#xff08;Distributed Denial of Service, DDoS&#xff09;攻击是一种利用大量受控设备&#xff08;通常是僵尸网络&#xff09;向目标系统发送大量请求或数据包&#xff0c;以耗尽目标系统的资源&#xff0c;导致其无法正常提供服务的攻击方式…

[集群聊天服务器]----(十)Nginx的tcp负载均衡配置--附带截图

接着上文&#xff0c;我们剖析了服务端和客户端的代码&#xff0c;但是单台服务器的并发量是有限的&#xff0c;面对并发量的要求&#xff0c;我们就需要引入Nginx来实现并发量的要求&#xff0c;将用户请求分发到不同的服务器上分担压力&#xff0c;这就是负载均衡。 选择负…