Optimized Belief Propagation (CPU and GPU)
ProcessBpOptimizedCPU.h
Go to the documentation of this file.
1 /*
2 Copyright (C) 2024 Scott Grauer-Gray
3 
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8 
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13 
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18 
28 #ifndef PROCESS_BP_OPTIMIZED_CPU_H_
29 #define PROCESS_BP_OPTIMIZED_CPU_H_
30 
31 #include <malloc.h>
32 #include <vector>
33 #include <algorithm>
34 #include <chrono>
35 #include <stdlib.h>
43 
44 //include for the "kernel" functions to be run on the CPU
45 #include "KernelBpStereoCPU.h"
46 
55 template<RunData_t T, unsigned int DISP_VALS, run_environment::AccSetting ACCELERATION>
56 class ProcessBpOptimizedCPU final : public ProcessBp<T, DISP_VALS, ACCELERATION>
57 {
58 public:
59  explicit ProcessBpOptimizedCPU(const ParallelParams& opt_cpu_params) :
60  ProcessBp<T, DISP_VALS, ACCELERATION>(opt_cpu_params) {}
61 
62 private:
63  run_eval::Status InitializeDataCosts(
64  const beliefprop::BpSettings& alg_settings,
65  const BpLevel<T>& current_bp_level,
66  const std::array<float*, 2>& images_target_device,
67  const beliefprop::DataCostsCheckerboards<T*>& data_costs_device) const override;
68 
69  run_eval::Status InitializeDataCurrentLevel(
70  const BpLevel<T>& current_bp_level,
71  const BpLevel<T>& prev_bp_level,
72  const beliefprop::DataCostsCheckerboards<T*>& data_costs_device,
73  const beliefprop::DataCostsCheckerboards<T*>& data_costs_device_write,
74  unsigned int bp_settings_num_disp_vals) const override;
75 
76  run_eval::Status InitializeMessageValsToDefault(
77  const BpLevel<T>& current_bp_level,
78  const beliefprop::CheckerboardMessages<T*>& messages_device,
79  unsigned int bp_settings_num_disp_vals) const override;
80 
81  run_eval::Status RunBPAtCurrentLevel(
82  const beliefprop::BpSettings& alg_settings,
83  const BpLevel<T>& current_bp_level,
84  const beliefprop::DataCostsCheckerboards<T*>& data_costs_device,
85  const beliefprop::CheckerboardMessages<T*>& messages_device,
86  T* allocated_memory) const override;
87 
88  run_eval::Status CopyMessageValuesToNextLevelDown(
89  const BpLevel<T>& current_bp_level,
90  const BpLevel<T>& next_bp_level,
91  const beliefprop::CheckerboardMessages<T*>& messages_device_copy_from,
92  const beliefprop::CheckerboardMessages<T*>& messages_device_copy_to,
93  unsigned int bp_settings_num_disp_vals) const override;
94 
95  float* RetrieveOutputDisparity(
96  const BpLevel<T>& current_bp_level,
97  const beliefprop::DataCostsCheckerboards<T*>& data_costs_device,
98  const beliefprop::CheckerboardMessages<T*>& messages_device,
99  unsigned int bp_settings_num_disp_vals) const override;
100 };
101 
102 //functions definitions related to running BP to retrieve the movement between the images
103 
104 //run the given number of iterations of BP at the current level using the given message values in global device memory
105 template<RunData_t T, unsigned int DISP_VALS, run_environment::AccSetting ACCELERATION>
107  const beliefprop::BpSettings& alg_settings,
108  const BpLevel<T>& current_bp_level,
109  const beliefprop::DataCostsCheckerboards<T*>& data_costs_device,
110  const beliefprop::CheckerboardMessages<T*>& messages_device,
111  T* allocated_memory) const
112 {
113  //at each level, run BP for numIterations, alternating between updating the messages between the two "checkerboards"
114  for (unsigned int iteration_num = 0; iteration_num < alg_settings.num_iterations; iteration_num++)
115  {
116  const beliefprop::CheckerboardPart checkerboard_part_update =
117  ((iteration_num % 2) == 0) ?
120 
121  using namespace beliefprop;
122  beliefprop_cpu::RunBPIterationUsingCheckerboardUpdates<T, DISP_VALS, ACCELERATION>(
123  checkerboard_part_update, current_bp_level.LevelProperties(),
124  data_costs_device[0], data_costs_device[1],
125  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
126  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
127  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
128  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
129  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
130  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
131  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
132  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
133  alg_settings.disc_k_bp, alg_settings.num_disp_vals, this->parallel_params_);
134  }
136 }
137 
138 //copy the computed BP message values from the current now-completed level to the corresponding slots in the next level "down" in the computation
139 //pyramid; the next level down is double the width and height of the current level so each message in the current level is copied into four "slots"
140 //in the next level down
141 //need two different "sets" of message values to avoid read-write conflicts
142 template<RunData_t T, unsigned int DISP_VALS, run_environment::AccSetting ACCELERATION>
144  const BpLevel<T>& current_bp_level,
145  const BpLevel<T>& next_bp_level,
146  const beliefprop::CheckerboardMessages<T*>& messages_device_copy_from,
147  const beliefprop::CheckerboardMessages<T*>& messages_device_copy_to,
148  unsigned int bp_settings_num_disp_vals) const
149 {
150  for (const auto& checkerboard_part : {beliefprop::CheckerboardPart::kCheckerboardPart0,
152  {
153  //call the kernel to copy the computed BP message data to the next level down in parallel in each of the two "checkerboards"
154  //storing the current message values
155  using namespace beliefprop;
156  beliefprop_cpu::CopyMsgDataToNextLevel<T, DISP_VALS, ACCELERATION>(
157  checkerboard_part, current_bp_level.LevelProperties(), next_bp_level.LevelProperties(),
158  messages_device_copy_from[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
159  messages_device_copy_from[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
160  messages_device_copy_from[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
161  messages_device_copy_from[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
162  messages_device_copy_from[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
163  messages_device_copy_from[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
164  messages_device_copy_from[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
165  messages_device_copy_from[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
166  messages_device_copy_to[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
167  messages_device_copy_to[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
168  messages_device_copy_to[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
169  messages_device_copy_to[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
170  messages_device_copy_to[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
171  messages_device_copy_to[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
172  messages_device_copy_to[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
173  messages_device_copy_to[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
174  bp_settings_num_disp_vals, this->parallel_params_);
175  }
177 }
178 
179 //initialize the data cost at each pixel with no estimated Stereo values...only the data and discontinuity costs are used
180 template<RunData_t T, unsigned int DISP_VALS, run_environment::AccSetting ACCELERATION>
182  const beliefprop::BpSettings& alg_settings, const BpLevel<T>& current_bp_level,
183  const std::array<float*, 2>& images_target_device, const beliefprop::DataCostsCheckerboards<T*>& data_costs_device) const
184 {
185  //initialize the data the the "bottom" of the image pyramid
186  beliefprop_cpu::InitializeBottomLevelData<T, DISP_VALS, ACCELERATION>(
187  current_bp_level.LevelProperties(),
188  images_target_device[0], images_target_device[1],
189  data_costs_device[0], data_costs_device[1],
190  alg_settings.lambda_bp, alg_settings.data_k_bp,
191  alg_settings.num_disp_vals, this->parallel_params_);
193 }
194 
195 //initialize the message values with no previous message values...all message values are set to 0
196 template<RunData_t T, unsigned int DISP_VALS, run_environment::AccSetting ACCELERATION>
198  const BpLevel<T>& current_bp_level,
199  const beliefprop::CheckerboardMessages<T*>& messages_device,
200  unsigned int bp_settings_num_disp_vals) const
201 {
202  using namespace beliefprop;
203  //initialize all the message values for each pixel at each possible movement to the default value in the kernel
204  beliefprop_cpu::InitializeMessageValsToDefaultKernel<T, DISP_VALS, ACCELERATION>(
205  current_bp_level.LevelProperties(),
206  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
207  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
208  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
209  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
210  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
211  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
212  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
213  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
214  bp_settings_num_disp_vals, this->parallel_params_);
215 
217 }
218 
219 
220 template<RunData_t T, unsigned int DISP_VALS, run_environment::AccSetting ACCELERATION>
222  const BpLevel<T>& current_bp_level,
223  const BpLevel<T>& prev_bp_level,
224  const beliefprop::DataCostsCheckerboards<T*>& data_costs_device,
225  const beliefprop::DataCostsCheckerboards<T*>& data_costs_device_write,
226  unsigned int bp_settings_num_disp_vals) const
227 {
228  const size_t offset_num{0};
229  for (const auto& [checkerboard_part, data_costs] : {
230  std::make_pair(
232  data_costs_device_write[0]),
233  std::make_pair(
235  data_costs_device_write[1])})
236  {
237  beliefprop_cpu::InitializeCurrentLevelData<T, DISP_VALS, ACCELERATION>(
238  checkerboard_part,
239  current_bp_level.LevelProperties(), prev_bp_level.LevelProperties(),
240  data_costs_device[0], data_costs_device[1],
241  data_costs,
242  ((int) offset_num / sizeof(float)),
243  bp_settings_num_disp_vals, this->parallel_params_);
244  }
246 }
247 
248 template<RunData_t T, unsigned int DISP_VALS, run_environment::AccSetting ACCELERATION>
250  const BpLevel<T>& current_bp_level,
251  const beliefprop::DataCostsCheckerboards<T*>& data_costs_device,
252  const beliefprop::CheckerboardMessages<T*>& messages_device,
253  unsigned int bp_settings_num_disp_vals) const
254 {
255  float* result_disp_map_device =
256  new float[current_bp_level.LevelProperties().width_level_ * current_bp_level.LevelProperties().height_level_];
257 
258  using namespace beliefprop;
259  beliefprop_cpu::RetrieveOutputDisparity<T, DISP_VALS, ACCELERATION>(
260  current_bp_level.LevelProperties(),
261  data_costs_device[0],
262  data_costs_device[1],
263  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
264  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
265  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
266  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart0)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
267  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesUCheckerboard)],
268  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesDCheckerboard)],
269  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesLCheckerboard)],
270  messages_device[static_cast<unsigned int>(CheckerboardPart::kCheckerboardPart1)][static_cast<unsigned int>(MessageArrays::kMessagesRCheckerboard)],
271  result_disp_map_device, bp_settings_num_disp_vals, this->parallel_params_);
272 
273  return result_disp_map_device;
274 }
275 
276 #endif //PROCESS_BP_OPTIMIZED_CPU_H_
File with namespace for enums, constants, structures, and functions specific to belief propagation pr...
Header file that contains information about the stereo sets used for evaluation of the bp implementat...
This header declares the kernel functions to run optimized belief propagation on CPU.
Declares child class of ParallelParams to store and process parallelization parameters to use in each...
Declares abstract class to run belief propagation on target device. Some of the class functions need ...
Contains namespace with enums and constants for implementation run evaluation.
Declares and defines structure that stores settings for current implementation run as well as functio...
Define constraints for data type in processing.
Class to store and retrieve properties of a bp processing level including a data type specified as a ...
Definition: BpLevel.h:60
const beliefprop::BpLevelProperties & LevelProperties() const
Return level properties as const reference to avoid copying and not allow it to be modified.
Definition: BpLevel.h:165
Abstract class for holding and processing parallelization parameters. Child class(es) specific to im...
Abstract class to run belief propagation on target device. Some of the class functions need to be ove...
Definition: ProcessBp.h:67
Child class of ProcessBp that defines functions used in processing bp in the optimized CPU implementa...
ProcessBpOptimizedCPU(const ParallelParams &opt_cpu_params)
Namespace for enums, constants, structures, and functions specific to belief propagation processing.
std::array< T, kNumCheckerboardParts > DataCostsCheckerboards
Define alias for two-element array with data costs for each bp processing checkerboard....
CheckerboardPart
Define the two checkerboard "parts" that the image is divided into.
std::array< std::array< T, kNumMessageArrays >, kNumCheckerboardParts > CheckerboardMessages
Define alias for array with message costs for each bp processing checkerboard. Each checkerboard mes...
Status
Enum for status to indicate if error or no error.
unsigned int height_level_
Definition: BpLevel.h:44
unsigned int width_level_
Definition: BpLevel.h:43
Structure to store the belief propagation settings including the number of levels and iterations.
Definition: BpSettings.h:87
unsigned int num_iterations
Definition: BpSettings.h:90
unsigned int num_disp_vals
Number of disparity values must be set for each stereo set.
Definition: BpSettings.h:101
float disc_k_bp
Discontinuity cost cap set to high value by default but is expected to be dependent on number of disp...
Definition: BpSettings.h:98