轮廓追踪算法

1. Contour Tracing Algorithms

• Square Tracing Algorithm
• Moore-Neighbor Tracing
• Radial Sweep
• Theo Pavlidis’ Algorithm

2. Square Tracing Algorithm

• 扫描得到起始点
• 当前为黑色点，左转
• 当前点位白色点，右转

• 循环直到回到起始点

  注意：左转和右转是针对当前循环的位置
  -------------
  |   | 1 |   |
  -------------
  | 2 | x | 0 |
  -------------
  |   | 3 |   |
  -------------
  
  如果当前点位置为x，前向点位置为0时：
      left = 3; right = 1
      
  如果当前点位置为x，前向点位置为3时：
      left = 2; right = 0

• 无法追踪斜线，改进：终止条件改为访问起始点多次

• 通过4邻域而非8领域追踪边界

3. Moore-Neighbor Tracing

• 摩尔邻域

  -------------
  | 3 | 2 | 1 |
  -------------
  | 4 | x | 0 |
  -------------
  | 5 | 6 | 7 |
  -------------
  
  cur_id  pre_id  pre_id_next_loop
  0           7       5
  1           0       7
  2           1       7
  3           2       1
  4           3       1
  5           4       3
  6           5       3
  7           6       5

• 顺时针扫描当前边界点，直到遇到黑色像素

• 退回白色像素，重复扫描操作

vector<vtkSmartPointer<vtkPoints>> ContourTracing::GetContours()
{
	//		-------------
	//		| 0 | 1 | 2 |
	//		-------------
	//		| 7 | x | 3 |
	//		-------------
	//		| 6 | 5 | 4 |
	//		-------------
	int* dims = input->GetDimensions();

	vtkSmartPointer<vtkImageData> imageData =
		vtkSmartPointer<vtkImageData>::New();
	imageData->SetDimensions(dims[0], dims[1], 1);
	imageData->AllocateScalars(VTK_SHORT, 1);
	for (int y = 0; y < dims[1]; y++)
	{
		for (int x = 0; x < dims[0]; x++)
		{
			short* pixel = static_cast<short*>(imageData->GetScalarPointer(x, y, 0));
			pixel[0] = 0;
		}
	}

	const int N8[8][2] =
	{
		{ -1,-1 },{ 0, -1 },{ 1,-1 },{ 1,0 },{1,1},{0,1},{-1,1},{-1,0}
	};
	const int N4[4] = { 7,1,3,5 };

	int start_idx[2];
	int curr_idx[2];
	int tmp_idx[2];

	// 1. 扫描找到白色点
	for (int y = 0; y < dims[1]; y++)
	{
		for (int x = 0; x < dims[0]; x++)
		{
			unsigned char* pixel = static_cast<unsigned char*>(input->GetScalarPointer(x, y, 0));
			if (pixel[0] != 0)
			{
				start_idx[0] = x;
				start_idx[1] = y;
				break;
			}
		}
	}
	cout << start_idx[0] << endl << start_idx[1] << endl;
	// 2. 初始化
	curr_idx[0] = start_idx[0];
	curr_idx[1] = start_idx[1];

	int pre_id = 0;
	
	if (curr_idx[0] - 1 >= 0)
	{
		pre_id = 7;
	}
	else if (curr_idx[0] - 1 == 0 && curr_idx[1] - 1 >= 0)
	{
		pre_id = 1;
	}
	else
	{
		cout << "error for find the first idx" << endl;
	}

	//vector<vector<int>> pts;
	//vector<int> pt(2, 0);
	//pt[0] = start_idx[0];
	//pt[1] = start_idx[1];
	//pts.push_back(pt);
	int count = 0;
	do
	{
		//cout << count++ << endl;
		//if (count == 1000)
		//	break;
		for (int i = 1; i < 8; i++)
		{
			int id = (i + pre_id) % 8;
			tmp_idx[0] = curr_idx[0] + N8[id][0];
			tmp_idx[1] = curr_idx[1] + N8[id][1];

			unsigned char* pixel = static_cast<unsigned char*>(input->GetScalarPointer(tmp_idx[0], tmp_idx[1], 0));
			if (pixel[0] != 0)
			{
				short* pixel = static_cast<short*>(imageData->GetScalarPointer(tmp_idx[0], tmp_idx[1], 0));
				pixel[0] = 255;
				curr_idx[0] = tmp_idx[0];
				curr_idx[1] = tmp_idx[1];

				pre_id = (id - 1 + 8) % 8;
				pre_id = N4[pre_id / 2];
				break;
			}
			else
			{
				short* pixel = static_cast<short*>(imageData->GetScalarPointer(tmp_idx[0], tmp_idx[1], 0));
				pixel[0] = 128;
			}
		}
		//vector<int> pt(2, 0);
		//pt[0] = curr_idx[0];
		//pt[1] = curr_idx[1];
		//pts.push_back(pt);
	} while (start_idx[0] != curr_idx[0] || start_idx[1] != curr_idx[1]);



	//for (size_t i = 0; i < pts.size(); i++)
	//{
	//	short* pixel = static_cast<short*>(imageData->GetScalarPointer(pts[i][0], pts[i][1], 0));
	//	pixel[0] = 128;
	//}
	vtkSmartPointer<vtkMetaImageWriter> writer = vtkSmartPointer<vtkMetaImageWriter>::New();
	writer->SetInputData(imageData);
	writer->SetFileName("binary_res.mha");
	writer->Write();
	return vector<vtkSmartPointer<vtkPoints>>();
}

参考

[1].http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/alg.html