作业帮什么是图像离散化
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/01 10:19:54
什么是图像离散化
什么是图像离散化
什么是图像离散化
如果说今年这时候OIBH问得最多的问题是二分图,那么去年这时候问得最多的算是离散化了.对于“什么是离散化”,搜索帖子你会发现有各种说法,比如“排序后处理”、“对坐标的近似处理”等等.哪个是对的呢?哪个都对.关键在于,这需要一些例子和不少的讲解才能完全解释清楚.
离散化是程序设计中一个非常常用的技巧,它可以有效的降低时间和空间复杂度.其基本思想就是在众多可能的情况中“只考虑我需要用的值”.下面我将用三个例子说明,如何运用离散化改进一个低效的,甚至根本不可能实现的算法.
《算法艺术与信息学竞赛》中的计算几何部分,黄亮举了一个经典的例子,我认为很适合用来介绍离散化思想.这个问题是UVA10173题目意思很简单,给定平面上n个点的坐标,求能够覆盖所有这些点的最小矩形面积.这个问题难就难在,这个矩形可以倾斜放置（边不必平行于坐标轴）.这里的倾斜放置很不好处理,因为我们不知道这个矩形最终会倾斜多少度.假设我们知道这个矩形的倾角是α,那么答案就很简单了：矩形面积最小时四条边一定都挨着某个点.也就是说,四条边的斜率已经都知道了的话,只需要让这些边从外面不断逼近这个点集直到碰到了某个点.你不必知道这个具体应该怎么实现,只需要理解这可以通过某种方法计算出来,毕竟我们的重点在下面的过程.
我们的算法很显然了：枚举矩形的倾角,对于每一个倾角,我们都能计算出最小的矩形面积,最后取一个最小值.
这个算法是否是正确的呢?我们不能说它是否正确,因为它根本不可能实现.矩形的倾角是一个实数,它有无数种可能,你永远不可能枚举每一种情况.我们说,矩形的倾角是一个“连续的”变量,它是我们无法枚举这个倾角的根本原因.我们需要一种方法,把这个“连续的”变量变成一个一个的值,变成一个“离散的”变量.这个过程也就是所谓的离散化.
我们可以证明,最小面积的矩形不但要求四条边上都有一个点,而且还要求至少一条边上有两个或两个以上的点.试想,如果每条边上都只有一个点,则我们总可以把这个矩形旋转一点使得这个矩形变“松”,从而有余地得到更小的矩形.于是我们发现,矩形的某条边的斜率必然与某两点的连线相同.如果我们计算出了所有过两点的直线的倾角,那么α的取值只有可能是这些倾角或它减去90度后的角（直线按“\”方向倾斜时）这么C(n,2)种.我们说,这个“倾角”已经被我们“离散化”了.虽然这个算法仍然有优化的余地,但此时我们已经达到了本文开头所说的目的.
对于某些坐标虽然已经是整数（已经是离散的了）但范围极大的问题,我们也可以用离散化的思想缩小这个规模.最近搞模拟赛Vijos似乎火了一把,我就拿两道Vijos的题开刀. VOJ1056[2]永远是离散化的经典问题.大意是给定平面上的n个矩形（坐标为整数,矩形与矩形之间可能有重叠的部分）,求其覆盖的总面积.平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”（把矩形所在的位置填上True）.可惜这个想法在这里有些问题,因为这个题目中坐标范围相当大（坐标范围为-10^8到10^8之间的整数）.但我们发现,矩形的数量n