poj1009 Edge Detection 解题报告

http://poj.org/problem?id=1009

主要解决三问题1. 图像的存储

输入采用的是RLE编码，存储也采用类似的方式，但要做点变换。比如输入

7
15 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0

经过变换，得到

7

15 4

100 19

25 21

175 23

25 28

175 30

25 35

其实就是把run length修改成了index分界值。这样做的好处是：要知道第n个像素的值，直接跟其中index分界值进行比较即可，简化了查找过程。

2. 每个像素edge值的计算

按照题目的要求，每个像素edge值是该像素与8邻域的最大差值。可以采用这样的处理方法：为8领域设置标志位，初始化均为true，表示邻域存在，然后根据像素的index判断它是否在图像的边界上，比如左上角的像素，其左边和上边的领域都不存在，根据不同的情况，对邻域的标志位进行更新。最后，只考虑标志位为true的领域，取它的值与当前像素值求差值，进而确定edge值。

3. 提速的技巧

逐像素进行处理一定会超时的，这里至少有两个提速的技巧。一是多行像素相同的情况，这时将有一连串值为0的edge；二是多列像素布局相同的情况，这时将有一连串相同edge值。下面是上述两种情况的例子

2

5 5000000

250 5000000

0 0

5000000

5 5000000

250 5000000

0 0

0

解题代码

#include <stdio.h>#include <stdlib.h>// struct BLOCKstruct BLOCK{short value;int   position;};const int N = 1005;// CRLEImage// class for run length encoded imageclass CRLEImage{private:BLOCK m_data[N];int   m_count;int   m_width;public:// constructorCRLEImage() : m_count(0), m_width(0){m_data[0].position = 0;m_data[0].value   = -1;}// Scanbool Scan(){int width, value, run_length;scanf("%d", &width);if( width == 0 ) {printf("0\n");return false;}m_width = width;int i = 1, index = 0;while(true){scanf("%d %d", &value, &run_length);if( value == 0 && run_length == 0)break;index += run_length;set_block(i, (short)value, index);++i;}m_count = i-1;return true;}// Processvoid Process(){printf("%d\n", m_width);short last_edge = calculate_edge(1, 1), edge;int last_idx = 1, idx = 2;for(int i = 1; i <= m_count; ++i){while(idx <= m_data[i].position){edge = calculate_edge(idx, i);// if edge value changeif(edge != last_edge){printf("%d %d\n", (int)last_edge, (idx - last_idx));last_idx = idx;last_edge = edge;}// same pixels in consecutive rowsif(last_edge == 0 && idx - m_data[i-1].position > m_width + 1  && m_data[i].position - idx > m_width)idx = m_data[i].position - m_width;else ++idx;// same pixels in consecutive columnsif(idx%m_width > 2 ){int same_length = m_width-1;int idx_arr[3] = { idx-m_width-2, idx-2, idx+m_width-2 };for( int j = 0; j < 3; ++j ){int location, temp;search_pixel(idx_arr[j], i, (idx_arr[j]<idx), location);if(location > 0){temp  = m_data[location].position - idx_arr[j];if(temp < same_length)same_length = temp;}}if(same_length > 2)idx += (same_length-2);}}}printf("%d %d\n", (int)edge, (idx - last_idx));printf("0 0\n");}private:// set blockvoid set_block(int index, short value, int position){m_data[index].value = value;m_data[index].position = position;}// search pixelshort search_pixel(int idx, int block, bool bBackward, int& location){if(idx < 1 || idx > m_data[m_count].position){location = -1;return 0;}int i = block;if(bBackward){for(i = block-1; i >= 0; --i)if(idx > m_data[i].position){location = i+1;return m_data[i+1].value;}}else{for(i = block; i <= m_count; ++i)if(idx <= m_data[i].position){location = i;return m_data[i].value;}}}// calculate edgeshort calculate_edge(int idx, int block){bool flag[8]; // does neighbor existfor(int i = 0; i < 8; ++i)flag[i] = true;// topif((idx - 1)/m_width == 0) flag[0] = flag[1] = flag[2] = false;// bottomif(idx + m_width > m_data[m_count].position) flag[5] = flag[6] = flag[7] = false;// left (especially when width is 1)if(m_width == 1 || idx % m_width  == 1 )flag[0] = flag[3] = flag[5] = false;// rightif(idx % m_width == 0 )flag[2] = flag[4] = flag[7] = false;// valid neighborshort base = m_data[block].value;short edge = 0;int nidx; // index of neighbor shortfor(int i = 0; i < 8; ++i)if(flag[i]){switch(i){case 0:case 1:case 2:nidx = idx - m_width + i - 1;break;case 3:nidx = idx - 1;break;case 4:nidx = idx + 1;break;default:nidx = idx + m_width + i - 6;}short neighbor;int location;neighbor = search_pixel(nidx, block, (nidx<idx), location);short temp = ((neighbor > base) ? (neighbor - base) : (base - neighbor));if(temp > edge)edge = temp;}return edge;}};// entry pointint main(){CRLEImage image;while( image.Scan() )image.Process();return 0;}