Edge Detection
| Time Limit: 1000MS | Memory Limit: 10000K |
| Total Submissions: 22604 | Accepted: 5311 |
Description
IONU Satellite Imaging, Inc. records and stores very large images using run length encoding. You are to write a program that reads a compressed image, finds the edges in the image, as described below, and outputs another compressed image of the detected edges.
A simple edge detection algorithm sets an output pixel's value to be the maximum absolute value of the differences between it and all its surrounding pixels in the input image. Consider the input image below:
The upper left pixel in the output image is the maximum of the values |15-15|,|15-100|, and |15-100|, which is 85. The pixel in the 4th row, 2nd column is computed as the maximum of |175-100|, |175-100|, |175-100|, |175-175|, |175-25|, |175-175|,|175-175|, and |175-25|, which is 150.
Images contain 2 to 1,000,000,000 (109) pixels. All images are encoded using run length encoding (RLE). This is a sequence of pairs, containing pixel value (0-255) and run length (1-109). Input images have at most 1,000 of these pairs. Successive pairs have different pixel values. All lines in an image contain the same number of pixels.
Input
Input consists of information for one or more images. Each image starts with the width, in pixels, of each image line. This is followed by the RLE pairs, one pair per line. A line with 0 0 indicates the end of the data for that image. An image width of 0 indicates there are no more images to process. The first image in the example input encodes the 5x7 input image above.
Output
Output is a series of edge-detected images, in the same format as the input images, except that there may be more than 1,000 RLE pairs.
Sample Input
7
15 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0
10
35 500000000
200 500000000
0 0
3
255 1
10 1
255 2
10 1
255 2
10 1
255 1
0 0
0
Sample Output
7
85 5
0 2
85 5
75 10
150 2
75 3
0 2
150 2
0 4
0 0
10
0 499999990
165 20
0 499999990
0 0
3
245 9
0 0
0
Hint
A brute force solution that attempts to compute an output value for every individual pixel will likely fail due to space or time constraints.
Source
Mid-Central USA 2000
題意
使用一種叫做“run length encoding”的方式來儲存大尺寸圖檔，該方法是通過記錄編碼值和編碼長度的對（number，length）來存儲圖檔。有一種簡單的edge detection算法是将圖像中的每一個點的值與他周圍的八個點求差，然後取絕對值的最大值。
現在的任務就是實作這個算法，輸入的圖檔是以run length encoding的形式表示的，同時也要求轉換後的圖檔也以run length encoding的形式表示。
思路
題意中說明圖檔的長度為10^9，是以不可能采用暴力計算法。從答案中可以看出，會有連續一段的相同輸入輸出，輸入的pair number不超過1000，數量上是很少的，是以可以采用跳躍編碼。
run length encoding編碼方法是記錄編碼值和該值的編碼長度，這裡長度可以用開始和結束位置代替，結束位置可以用下一個值的開始位置表示。這樣就變成記錄每一個出現的新值和出現的位置即可。
而edge detection中每一個新值的出現都是因為輸入圖檔中新值的出現。是以，隻要對輸入圖檔的每一個pair計算這個新值開始位置周圍8個像素值，并記錄位置即可。然後對所有計算的像素值根據位置排序，并且對像素值相同的格子進行合并就是所求結果。
上圖來自 POJ 1009 Edge Detection（圖像邊緣檢測）
我們使用跳躍編碼，記錄起始格子的num值和它的長度len，自然可以通過計算得到一個虛拟很長的輸入或是輸出數組（一維），再将一維數組轉換為虛拟二維數組，即對len進行累加，即為一維數組的索引值，像素值num即為一位數組中存儲的值，而轉換為二維數組，即為一位數組索引值對n取餘或是取整，之是以說是虛拟，就是不開辟空間進行存儲……
考慮到這裡，想到了使用map，map<int,int>，其中隻存儲連續段的起始格，對于輸入map<int,int> InMap和輸出map<int,int> OutMap，其key值用來存儲一位數組的索引值，value則用來存儲像素值num，為什麼用map呢，最重要的是它可以按照key值自動升序排列，計算每一個連續段起始格周圍的8個格子後，将計算得到的像素值和數組索引值插入map，他自動幫我們按照數組索引值排序了，這樣，當我們計算完畢之後，向前疊代輸出，省去了排序吧啦吧啦的麻煩，隻要向前疊代，并把像素值相同的格子忽略掉（因為他們應該屬于同一連續段的）就可以了。本小白感覺map大法好！
關于map==》C++ STL 中 map 容器
這時候，需要考慮一下特殊的格子，對于在二維數組邊界的格子，他的周圍不足8個格子，計算的時候當然要注意。
我們可以用簡單的取餘運算就把在最左邊一列、最右邊一列給篩選出來。這裡我們把連續段的長度進行求和為Max，即數組索引從0開始，且最大索引值不會超過Max，是以可以把最上面一行和最下面一行計算中的越界格子排掉。這裡需要考慮到每行隻有一列和兩列的情況！！
還有更值得我們注意的！！這裡也讓本小白WA了幾次，百思不得其解了好久……
那就是最後一行的第一個格子，由于它沒有下一行，是以它的像素值會發生變化
有朋友問為什麼最後一行的第一個格子需要考慮而别的行的第一個格子不需要考慮呢？
首先，如果像這樣像素值發生變化，自然會進行計算。
其次，如果像素值沒有發生變化，那無非就是擔心換行之後，格子上方和下方的格子的數值變化，拿上方格子數值變化為例，如果兩個格子（黃色）上方格子數值不一樣，那紫色格子的數值發生變化時，必然會計算黃色格子的數值，是以此處不需計算。其他情況同理。
而最下面一行的第一個格子，它的下面的格子不是數值發生變化，而是消失了，即可以了解為，它下面的格子數值發生了變化但是不會啟動計算過程，是以最下面一行的第一個格子是特殊的。
1 #include<iostream>
2 #include<map>
3 using namespace std;
4 /*
5 可以利用map<int,int>的first為下标，second為像素值
6 一個輸入map，一個輸出map
7 利用map的特性，輸出map插入後自動以first排序
8 輸出的時候周遊輸出map，如果second不同，則進行輸出
9
10 代碼很亂包括了我的測試代碼……
11 */
12 void Print(map<int,int> OutMap,int n,int Max)
13 {
14 long tempFirst = 0,tempSecond=0;
15 /*
16 map<int,int>::iterator iter = OutMap.begin();
17 for(iter;iter != OutMap.end();iter++)
18 {
19 cout<<iter->first<<" "<<iter->second<<endl;
20 }
21 */
22 map<int,int>::iterator iter1 = OutMap.begin();//向前疊代
23 tempFirst = iter1->first;tempSecond = iter1->second;
24 for(iter1;iter1 != OutMap.end();iter1++)
25 {
26 if(iter1->second != tempSecond)
27 {
28 cout<<tempSecond<<" "<<iter1->first-tempFirst<<endl;
29
30 tempSecond = iter1->second;
31 tempFirst = iter1->first;
32 }
33 }
34 cout<<tempSecond<<" "<<Max-tempFirst<<endl;
35
36 cout<<0<<" "<<0<<endl;
37 }
38 void Compute(map<int,int> In,int n,int Max)
39 {//計算輸出數組
40 /**/
41 map<int,int> OutMap;
42 int Count=0;//記錄數組下
43 int temp=0;
44 int arr[10] = {0,-n-1,-n,-n+1,-1,1,n-1,n,n+1,Max-n};
45 ///對In進行周遊
46 map<int,int>::iterator iter = In.begin();
47 for(iter;iter != In.end();iter++)
48 {
49 for(int i=0;i<10;i++)
50 {
51 if(i == 9) Count = arr[i];
52 else Count = iter->first + arr[i];//周圍8個像素的下标,包括自己
53 if(Count < 0 || Count >= Max)
54 {//下标越界
55 continue;
56 }
57 else if(Count%n == n-1 && iter->first%n == 0 && n!=2&& n!=1)
58 {//在最左邊一列，沒有左邊像素
59 continue;
60 }
61 else if(Count%n == 0 && iter->first%n == n-1 && n!=2&& n!=1)
62 {//在最右邊一列，沒有右邊像素
63 continue;
64 }
65 else{
66 map<int,int>::iterator CountIter = In.begin();//指針定位到中心
67 CountIter = In.upper_bound(Count);
68 CountIter--;
69 //cout<<"測試CountIter："<<CountIter->first<<" "<<CountIter->second<<endl;
70 ///計算目前像素的值
71 int Num = 0;
72 int tempNum = 0;
73 for(int j =1;j<9;j++)//考察周圍的八個點
74 {
75 temp = Count + arr[j];
76 if(temp<0 || temp>=Max || temp%n==n-1&&Count%n==0&&n!=2 || temp%n==0&&Count%n==n-1&&n!=2)
77 {
78 continue;
79 }else{
80 map<int,int>::iterator tempIter;
81 tempIter = In.upper_bound(temp);//第一個大于temp的位置
82 //cout<<"測試tempIter："<<tempIter->first<<" "<<tempIter->second<<endl;
83 tempIter--;
84 //cout<<"測試tempIter2："<<tempIter->first<<" "<<tempIter->second<<endl;
85 tempNum = CountIter->second - tempIter->second;
86 if(tempNum < 0) tempNum = -1 * tempNum;
87 }
88 if(tempNum > Num) Num = tempNum;
89 }
90 ///插入到OutMap
91 OutMap.insert(pair<int,int>(Count,Num));
92 }
93 }
94 }
95 Print(OutMap,n,Max);
96 OutMap.clear();
97 }
98
99 int main()
100 {
101 int n;
102 map<int,int> InMap;
103
104 cin>>n;
105 cout<<n<<endl;
106 while(n)
107 {
108
109 int num,len;
110 long Count = 0;
111 ///擷取輸入數組
112 cin>>num>>len;
113 while(len)
114 {
115 InMap.insert(pair<int,int>(Count,num));
116 Count += len;//虛拟數組下标增加
117 cin>>num>>len;
118 }
119 InMap.insert(pair<int,int>(1000000020,111));
120 /*
121 map<int,int>::iterator iter;//向前疊代
122 for(iter = InMap.begin();iter != InMap.end();iter++)
123 {
124 cout<<iter->first<<","<<iter->second<<endl;
125 }
126 */
127 ///輸入結束，進行輸出數組的計算
128 Compute(InMap,n,Count);
129 InMap.clear();
130 cin>>n;
131 cout<<n<<endl;
132 }
133
134
135 return 0;
136 } 轉載于:https://www.cnblogs.com/yxh-amysear/p/8287693.html